Optimal all-to-all personalized exchange in a class of opticalmultistage networks

All-to-all personalized exchange is one of the most dense collective communication patterns and it occurs in many important parallel computing/networking applications. In this paper, we look into the issue of realizing an all-to-all personalized exchange in a class of optical multistage networks. Advances in electrooptic technologies have made optical communication a promising networking choice to meet the increasing demands for high channel bandwidth and low communication latency of high-performance computing/communication applications. Although optical multistage networks hold great promise and have demonstrated advantages over their electronic counterpart, they also hold their own challenges. Due to the unique properties of optics, crosstalk in optical switches should be avoided to make them work properly. In this paper, we provide a systematic scheme for realizing an all-to-all personalized exchange in a class of unique-path optical multistage networks crosstalk-free. The basic idea of realizing an all-to-all personalized exchange in such a multistage network is to transform it to multiple semipermutations and ensure that each of them can be realized crosstalk-free in a single pass. As can be seen, the all-to-all personalized exchange algorithm we propose has O(n) time complexity for n processors, which is optimal for an all-to-all personalized exchange. The optimal time complexity combined with the property of a single input/output port per processor suggests that a multistage network could be a better choice for implementing an all-to-all personalized exchange due to its shorter communication latency and better scalability     

Optimal NODUP all-to-all broadcast schemes in distributed computingsystems

Broadcast, referring to a process of information dissemination in a distributed system whereby a message originating from a certain node is sent to all other nodes in the system, is a very important issue in distributed computing. All-to-all broadcast means the process by which every node broadcasts its certain piece of information to all other nodes. In this paper, we first develop the optimal all-to-all broadcast scheme for the case of one-port communication, which means that each node can only send out one message in one communication step, and then, extend our results to the case of multi-port communication, i.e., k-port communication, meaning that each node can send out k messages in one communication step. We prove that the proposed schemes are optimal for the model considered in the sense that they not only require the minimal number of communication steps, but also incur the minimal number of messages     

Energy efficient all-to-all broadcast in all-wireless networks

All-to-all broadcast is a communication pattern in which every node initiates a broadcast. In this paper, we investigate the problem of building a unique cast tree of minimum total energy, which we call Minimum Unique Cast (MUC) tree, to be used for all-to-all broadcast. The MUC tree is unoriented and unrooted. We study three known heuristics for the minimum-energy broadcast problem: the Broadcast Incremental Power (BIP) algorithm, the Wireless Multicast Advantage-conforming Minimum Spanning Tree (WMA-conforming MST) algorithm, and the Iterative Maximum-Branch Minimization (IMBM) algorithm. Experimental results conducted on various types of networks are reported. We show that neither of these methods is best overall for building all-to-all broadcast trees.     

Multi-hop all-to-all optical routings in Cartesian product networks

This paper considers the wavelength assignment problem for Cartesian product networks with multi-hops. An upper bound of the (uniform) wavelength index for Cartesian product networks with single-hop is established. This result leads to a consequence for the nth power of an arbitrary network with k-hops. In particular, if k=1, this bound partially generalizes the results of Pankaj [R.K. Pankaj, Architectures for linear lightwave networks, PhD thesis, Dept. of Electrical Engineering and Computer Science, MIT, Cambridge, MA, 1992], Bermond et al. [J.-C. Bermond, L. Gargano, S. Perennes, A.A. Rescigno, U. Vaccaro, Efficient collective communication in optical networks, Theoret. Comput. Sci. 233 (2000) 165-189] and Beauquier [B. Beauquier, All-to-all communication for some wavelength-routed all-optical networks, Networks 33 (1999) 179-187] for hypercubes and Hamming graphs. As an application, a tight upper bound for Hamming graph with k hops is established and a corresponding open problem is also proposed.     

Multihop all-to-all broadcast on WDM optical networks

Wavelength-division multiplexing (WDM) optical networks provide huge bandwidth by allowing multiple data streams transmitted simultaneously along the same optical fiber, with each stream assigned a distinct wavelength. A key issue on WDM optical networks is to minimize the number of wavelengths for communications. All-to-all broadcast (gossiping) is a fundamental communication application on computer/communication networks. It is known that the minimum numbers of wavelengths for realizing gossiping in one-hop of optical routing on the ring and the two-dimensional torus of N nodes are cN/sup 2/ and cN/sup 3/2/, c /spl ap/ 1/8, respectively. These numbers can be too large even for moderate values of N. One approach to reduce the number of wavelengths is to realize gossiping in multihops of routing. We give routing algorithms which realize gossiping in k-hops (k /spl ges/ 2) by O(N/sup 1+1/k/) wavelengths on the ring, O(N/sup 1+1/(2k)/) wavelengths on the 2D torus, and O(N/sup 1+1/(3k)/) wavelengths on the 3D torus on a simple multihop routing model. We also discuss the multihop routing for gossiping on a merge model. We give the upper bounds on the numbers of wavelengths for gossiping in two-hops and three-hops for the ring, 2D torus, and 3D torus on the merge model.     

Efficient implementations of all-to-all broadcasting in mobile ad hoc networks

In order to ease the challenging task of information dissemination in a MANET, we employ a legend: a data structure passed around a network to share information with all the mobile nodes. Our motivating application of the legend is sharing location information. Previous research shows that a simplistic legend performs better than other location services in the literature. To realize the full potential of legend-based location services, we propose three methods for the legend to traverse a network and compare their performance in simulation. Two of our proposed methods are novel, and the third is an improvement on an existing method. We also evaluate several general improvements to the traversal methods, and describe our way of making the legend transmission reliable. The result is a simple, lightweight location service that makes efficient use of network resources. Beyond using the legend as a location service, we discuss several implementation aspects of providing an efficient all-to-all broadcast operation, including legend reliability, preventing duplicate legends, using a legend in dynamic networks, and working with non-synchronized clocks. We also provide pseudocode for our legend traversal methods to aid implementation.     

All-to-all personalized communication in multidimensional torus andmesh networks

All-to-all personalized communication commonly occurs in many important parallel algorithms, such as FFT and matrix transpose. This paper presents new algorithms for all-to-all personalized communication or complete exchange in multidimensional torus- or mesh-connected multiprocessors. For an R×C torus or mesh where R⩽C, the proposed algorithms have time complexities of O(C) message startups and O(RC²) message transmissions. The algorithms for three- or higher-dimensional tori or meshes follow a similar structure. Unlike other existing message-combining algorithms in which the number of nodes in each dimension should be a power-of-two and square, the proposed algorithms accommodate non-power-of-two tori or meshes where the number of nodes in each dimension need not be power-of-two and square. In addition, destinations remain fixed over a larger number of steps in the proposed algorithms, thus making them amenable to optimizations. Finally, the data structures used are simple, hence making substantial savings of message-rearrangement time     

Generalized framework for personalized recommendations in agent networks

An agent network can be modeled as a directed weighted graph whose vertices represent agents and edges represent a trust relationship between the agents. This article proposes a new recommendation approach, dubbed LocPat, which can recommend trustworthy agents to a requester in an agent network. We relate the recommendation problem to the graph similarity problem, and define the similarity measurement as a mutually reinforcing relation. We understand an agent as querying an agent network to which it belongs to generate personalized recommendations. We formulate a query into an agent network as a structure graph applied in a personalized manner that reflects the pattern of relationships centered on the requesting agent. We use this pattern as a basis for recommending an agent or object (a vertex in the graph). By calculating the vertex similarity between the agent network and a structure graph, we can produce a recommendation based on similarity scores that reflect both the link structure and the trust values on the edges. Our resulting approach is generic in that it can capture existing network-based approaches merely through the introduction of appropriate structure graphs. We evaluate different structure graphs with respect to two main kinds of settings, namely, social networks and ratings networks. Our experimental results show that our approach provides personalized and flexible recommendations effectively and efficiently based on local information.     

Optimal polling in communication networks

Polling is the process in which an issuing node of a communication network (polling station) broadcasts a query to every other node in the network and waits to receive a unique response from each of them. Polling can be thought of as a combination of broadcasting and gathering and finds wide applications in the control of distributed systems. In this paper, we consider the problem of polling in minimum time. We give a general lower bound on the minimum number of time units to accomplish polling in any network and we present optimal polling algorithms for several classes of graphs, including hypercubes and recursively decomposable Cayley graphs     

On general results for all-to-all broadcast

All-to-all broadcast refers to the process by which every node broadcasts its certain piece of information to all other nodes in the system. In this paper, we develop all-to-all broadcast schemes by dealing with two classes of schemes. A prior scheme based on generation of minimal complete sets is first described, and then a new scheme based on propagation of experts is developed. The former always completes the broadcasting in the minimal number of steps and the latter is designed to minimize the number of messages. Performance of these two classes of schemes is comparatively analyzed. The all-to-all broadcast scheme desired can be derived by combining the advantages of these two classes of schemes     

Optimal total exchange in Cayley graphs

Consider an interconnection network and the following situation: Every node needs to send a different message to every other node. This is the total exchange or all-to-all personalized communication problem, one of a number of information dissemination problems known as collective communications. Under the assumption that a node can send and receive only one message at each step (single-port model), it is seen that the minimum time required to solve the problem is governed by the status (or total distance) of the nodes in the network. We present a time-optimal solution for any Cayley network. Rings, hypercubes, cube-connected cycles, and butterflies are some well-known Cayley networks which can take advantage of our method. The solution is based on a class of algorithms which we call node-invariant algorithms and which behave uniformly across the network     

Efficient algorithms for all-to-all communications in multiportmessage-passing systems

We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-to-all personalized communication) and concatenation (or all-to-all broadcast). We assume a model of a fully connected message-passing system, in which the performance of any point-to-point communication is independent of the sender-receiver pair. We also assume that each processor has k⩾1 ports, through which it can send and receive k messages in every communication round. The complexity measures we use are independent of the particular system topology and are based on the communication start-up time, and on the communication bandwidth     

Practical all-to-all propagators for lattice QCD

A new method for computing all elements of the lattice quark propagator is proposed. The method combines the spectral decomposition of the propagator, computing the lowest eigenmodes exactly, with noisy estimators which are ‘diluted’, i.e. taken to have support only on a subset of time, space, spin or color. We find that the errors are dramatically reduced compared to traditional noisy estimator techniques.     

Block-based neural networks for personalized ECG signal classification.

This paper presents evolvable block-based neural networks (BbNNs) for personalized ECG heartbeat pattern classification. A BbNN consists of a 2-D array of modular component NNs with flexible structures and internal configurations that can be implemented using reconfigurable digital hardware such as field-programmable gate arrays (FPGAs). Signal flow between the blocks determines the internal configuration of a block as well as the overall structure of the BbNN. Network structure and the weights are optimized using local gradient-based search and evolutionary operators with the rates changing adaptively according to their effectiveness in the previous evolution period. Such adaptive operator rate update scheme ensures higher fitness on average compared to predetermined fixed operator rates. The Hermite transform coefficients and the time interval between two neighboring R-peaks of ECG signals are used as inputs to the BbNN. A BbNN optimized with the proposed evolutionary algorithm (EA) makes a personalized heartbeat pattern classifier that copes with changing operating environments caused by individual difference and time-varying characteristics of ECG signals. Simulation results using the Massachusetts Institute of Technology/Beth Israel Hospital (MIT-BIH) arrhythmia database demonstrate high average detection accuracies of ventricular ectopic beats (98.1%) and supraventricular ectopic beats (96.6%) patterns for heartbeat monitoring, being a significant improvement over previously reported electrocardiogram (ECG) classification results.     

Optimal task assignment in homogeneous networks

This paper considers the problem of assigning the tasks of a distributed application to the processors of a distributed system such that the sum of execution and communication costs is minimized. Previous work has shown this problem to be tractable for a system of two processors or a linear array of N processors, and for distributed programs of serial parallel structures. Here we focus on the assignment problem on a homogeneous network, which is composed of N functionally-identical processors, each with its own memory. Some processors in the network may have unique resources, such as data files or certain peripheral devices. Certain tasks may have to use these unique resources; they are called attached tasks. The tasks of a distributed program should therefore be assigned so as to make use of specific resources located at certain processors in the network while minimizing the amount of interprocessor communication. The assignment problem in such a homogeneous network is known to be NP-hard even for N=3, thus making it intractable for a network with a medium to large number of processors. We therefore focus on task assignment in general array networks, such as linear arrays, meshes, hypercubes, and trees. We first develop a modeling technique that transforms the assignment problem in an array or tree into a minimum-cut maximum-flow problem. The assignment problem is then solved for a general array or tree network in polynomial time     

Optimal dynamic scheduling in Jackson networks

A Jackson-like network that supports J types of interactive traffic (e.g., interactive messages) as well as I types of noninteractive traffic (e.g., file transfers, facsimile) is considered. The service-time distributions and the internal routing are homogeneous for all traffic types but can be node (queue) dependent. The problem is to find a scheduling control that minimizes a weighted sum of the average end-to-end delay for the interactive types and at the same time ensures that the average end-to-end delays for the interactive types will be below given design constraints. Conservation laws are first established and shown to yield the base of a polymatroid. The optimal control problem is then transformed into a linear program with the feasible region being the polymatroid base truncated by delay constraints. An optimal control is identified that partitions the traffic types into I+r (0⩽r⩽J) ordered groups and applies a strict priority rule among the groups. An algorithm is developed that does the grouping and solves the optimization problem. A decentralized implementation of the optimal control is also discussed     

A framework for personalized recommendation with conditional generative adversarial networks

Knowledge and Information Systems - Recommender systems suffer from interaction data sparsity in reality. Recently, generative adversarial network-based recommender systems have shown the potential...     

Optimal layouts of midimew networks

Midimew networks are mesh-connected networks derived from a subset of degree-4 circulant graphs. They have minimum diameter and average distance among all degree-4 circulant graphs, and are better than some of the most common topologies for parallel computers in terms of various cost measures. Among the many midimew networks, the rectangular ones appear to be most suitable for practical implementation. Unfortunately, with the normal way of laying out these networks on a 2D plane, long cross wires that grow with the size of the network exist. In this paper, we propose ways to lay out rectangular midimew networks in a 2D grid so that the length of the longest wire is at most a small constant. We prove that these constants are optimal under the assumption that rows and columns are moved as a whole during the layout process