Composite synchronization in parallel discrete-event simulation

This paper considers a technique for composing global (barrier-style) and local (channel scanning) synchronization protocols within a single parallel discrete-event simulation. Composition is attractive because it allows one to tailor the synchronization mechanism to the model being simulated. We first motivate the problem by showing the large performance gap that can be introduced by a mismatch of model and synchronization method. Our solution calls for each channel between submodels to be classified as synchronous or asynchronous. We mathematically formulate the problem of optimally classifying channels and show that, in principle, the optimal classification can be obtained in time proportional to max{C×log C, V×N}, where C is the number of channels, V the number of unique minimal delays on those channels, and N is the number of submodels. We then demonstrate an implementation which finds an optimal solution at runtime and consider its performance on network topologies, including one of the global Internet at the autonomous system level. We find that the automated method effectively determines channel assignments that maximize performance     

On Output Processes of Synchronization Queues

We consider synchronization queues with finite or infinite buffers. There is one flow of tokens for each buffer. The input flow to each buffer, called a stream, is assumed to be a point process with finite intensity. Tokens arriving at each buffer have to wait to form a synchronized group and depart the system. We are concerned with output processes in this queue. The output processes of synchronization queues with some buffers having infinite capacities are studied. Further, we consider synchronization queues with two finite buffers and discuss the system state at output points in time. For these problems, some results that are already known are reviewed and some new results are introduced.     

Gradient clock synchronization

We introduce the distributed gradientclock synchronization problem. As in traditional distributed clock synchronization, we consider a network of nodes equipped with hardware clocks with bounded drift. Nodes compute logical clock values based on their hardware clocks and message exchanges, and the goal is to synchronize the nodes' logical clocks as closely as possible, while satisfying certain validity conditions. The new feature of gradient clock synchronization GCS for short) is to require that the skew between any two nodesy' logical clocks be bounded by a nondecreasing function of the uncertainty in message delay (call this the distance) between the two nodes, and other network parameters. That is, we require nearby nodes to be closely synchronized, and allow faraway nodes to be more loosely synchronized. We contrast GCS with traditional clock synchronization, and discuss several practical motivations for GCS, mostly arising in sensor and ad-hoc networks. Our main result is that the worst case clock skew between two nodes at distance d or less from each other is Ω(d + , where D is the diameter of the network. This means that clock synchronization is not a localproperty, in the sense that the clock skew between two nodes depends not only on the distance between the nodes, but also on the size of the network. Our lower bound implies, for example, that the TDMA protocol with a fixed slot granularity will fail as the network grows, even if the maximum degree of each node stays constant.     

Almost output synchronization for heterogeneous time‐varying networks for a class of non‐introspective,nonlinear agents without exchange of controller states

We consider almost output synchronization for directed heterogeneous time‐varying networks where agents are non‐introspective (i.e., agents have no access to their own states or outputs) in the presence of external disturbances. The nonlinear agents have a triangular structure and are globally Lipschitz continuous. The network can be time‐varying with network switches occurring at arbitrary moments. A purely decentralized time‐invariant protocol based on a low‐gain and high‐gain method is designed for each agent to achieve almost output synchronization while reducing the impact of disturbances on the output synchronization error. Copyright © 2016 John Wiley & Sons, Ltd.     

Passivity-based designs for synchronized path-following

We consider a formation control system where individual systems are controlled by a path-following design and the path variables are to be synchronized. We first show a passivity property for the path-following system, and next, combine this with a passivity-based synchronization algorithm developed in Arcak [2007. Passivity as a design tool for group coordination. IEEE Transactions on Automatic Control, in press]. The passivity approach expands the classes of synchronization schemes available to the designer. This generality offers the possibility to optimize controllers to, e.g., improve robustness and performance. Two designs are developed in the proposed passivity framework: the first employs the path error information in the synchronization loop, while the second only uses synchronization errors. A sampled-data design, where the path variables are updated in discrete-time and the path-following controllers are updated in continuous time, is also developed.     

Interactive-Rate Animation Generation by Parallel Progressive Ray-Tracing on Distributed-Memory Machines

We describe a dynamic load-balancing algorithm for ray-tracing by progressive refinement on a distributed-memory parallel computer. Parallelization of progressive ray-tracing for single images is difficult because of the inherent sequential nature of the sample location generation process, which is optimized (and different) for any given image. Parallelization of progressive ray-tracing when generating image sequences at a fixed interactive rate is even more difficult, because of the time and synchronization constraints imposed on the system. The fixed frame rate requirement complicates matters and even renders meaningless traditional measures of parallel system performance (e.g., speedup). We show how to overcome these problems, which, to the best of our knowledge, have not been treated before. Exploiting the temporal coherence between frames enables us to both accelerate rendering and improve the load-balance throughout the sequence. Our dynamic load-balance algorithm combines local and global methods to account not only for rendering performance, but also for communication overhead and synchronization issues. The algorithm is shown to be robust to the harsh environment imposed by a time-critical application, such as the one we consider.     

A new set of sufficient conditions based on coupling parameters for synchronization of Hopfield like Chaotic Neural Networks

In this paper, we consider a Hopfield like Chaotic Neural Networks which have both self-coupling and non-invertible activation functions. We show that the interactions between neurons can be used as a means of chaos generation or suppression to neuron’s outputs when more adaptability or stability is required. Furthermore, a new set of sufficient conditions based on coupling weights is proposed so that the synchronization of all neuron’s outputs with each other is guaranteed, when all neuron’s have identical activation functions. Finally, the effectiveness of the proposed approach is evaluated by performing simulations on three illustrative examples.     

Transshipment and safety stock under stochastic supply interruption in a production system

We consider a two-echelon system with one source supplying two locations with the same product. The random occurrence of interruptions at the source where downtime is also stochastic can result in stockouts at the two receiving locations. Our model studies the benefit of allowing each location to carry a safety stock where holding costs can be different at each location. The objective is to reduce overall cost at both locations. In some cases it is optimal to allow for a transshipment of inventory from the safety stock of one location to the other. We jointly solve for the optimal safety stock at each location and the optimal amount to be transshipped from a location to the other. We show that by conditioning on the transshipment direction the total cost becomes convex as a function of the safety stock levels at the receiving locations and the amount to be transshipped from a location to the other. Numerical examples are presented for different system cost parameters and probability distributions.     

Learning multi-agent communication with double attentional deep reinforcement learning

Autonomous Agents and Multi-Agent Systems - We consider an agent seeking to obtain an item, potentially available at different locations in a physical environment. The traveling costs between...     

Exploiting wavefront parallelism on large-scale shared-memorymultiprocessors

Wavefront parallelism, in which parallelism is limited to hyperplanes in an iteration space, can arise when compilers apply tiling to loop nests to enhance locality. Previous approaches for scheduling wavefront parallelism focused on maximizing parallelism; balancing workloads, and reducing synchronization. In this paper, we show that on large-scale shared-memory multiprocessors, locality is a crucial factor. We make the distinction between intratile and intertile locality and show that as the number of processors grows, intertile locality becomes more important. We consider and experimentally evaluate existing strategies for scheduling wavefront parallelism. We show that dynamic self-scheduling can be efficiently used on a small number of processors, but performs poorly at large scale because it does not enhance intertile locality. By contrast, static scheduling strategies enhance intertile locality for small tiles, maintaining parallelism and resulting in better performance at large scale. Results from a Convex SPP1000 multiprocessor demonstrate the importance of taking intertile locality into account. Static scheduling outperforms dynamic self-scheduling by a factor of up to 2.3 on 30 processors     

Image Transformations and Blurring

Since cameras blur the incoming light during measurement, different images of the same surface do not contain the same information about that surface. Thus, in general, corresponding points in multiple views of a scene have different image intensities. While multiple-view geometry constrains the locations of corresponding points, it does not give relationships between the signals at corresponding locations. This paper offers an elementary treatment of these relationships. We first develop the notion of "ideal” and "real” images, corresponding to, respectively, the raw incoming light and the measured signal. This framework separates the filtering and geometric aspects of imaging. We then consider how to synthesize one view of a surface from another; if the transformation between the two views is affine, it emerges that this is possible if and only if the singular values of the affine matrix are positive. Next, we consider how to combine the information in several views of a surface into a single output image. By developing a new tool called "frequency segmentation,” we show how this can be done despite not knowing the blurring kernel.     

Effect of node churn on frame interval for peer-to-peer video streaming with data-block synchronization mechanism

Coolstreaming is a mesh based peer-to-peer (P2P) video streaming system in which single video stream is decomposed into multiple sub-streams. A client-peer node retrieves the sub-streams from multiple parent-peer nodes, combining them into the original video stream. Each client-peer node has two buffers, a synchronization buffer and a cache buffer, and arriving data blocks are synchronized at the synchronization buffer and then forwarded to the cache buffer. In this buffering system, data-block synchronization is important to guarantee high video quality. In this paper, we consider the effect of churn on the performance of data-block synchronization scheme with which data blocks are simultaneously forwarded just after all the data blocks composing a macro data block arrive at the synchronization buffer. It is assumed that data blocks belonging to a sub-stream arrive at the client-peer node according to an interrupted Poisson process. The synchronization buffer is modeled as a multiple-buffer queueing system with homogeneous interrupted Poisson processes, and the mean forwarding interval is derived. Numerical examples show that the average forwarding interval increases as parent-peer nodes leave more frequently.     

Graphical models for integrating syllabic information

We present graphical model based methodology that enhances a speech recognizer with information about syllabic segmentations. The segmentations are specified by locations of syllable nuclei, and the graphical models are able to consider these locations as “soft” information. The graphs give improved discrimination between speech and noise when compared to a baseline model. When using locations derived from oracle information an overall improvement is shown, and when the oracle syllable nuclei are augmented with information about lexical stress the methods give additional improvements over locations alone.     

An Efficient Synchronization Mechanism for Mirrored Game Architectures

Existing online multiplayer games typically use a client-server model, which introduces added latency as well as a single bottleneck and single point of failure to the game. Distributed multiplayer games minimize latency and remove the bottleneck, but require special synchronization mechanisms to provide a consistent game for all players. Current synchronization methods have been borrowed from distributed military simulations and are not optimized for the requirements of fast-paced multiplayer games. In this paper we present a new synchronization mechanism, trailing state synchronization (TSS), which is designed around the requirements of distributed first-person shooter games.We look at TSS in the environment of a mirrored game architecture, which is a hybrid between traditional centralized architectures and the more scalable peer-to-peer architectures. Mirrored architectures allow for improved performance compared to client-server architectures while at the same time allowing for a greater degree of centralized administration than peer-to-peer architectures.We evaluate the performance of TSS and other synchronization methods through simulation and examine heuristics for selecting the synchronization delays needed for TSS.     

Anomaly detection in concurrent Java programs using dynamic data flow analysis

Concurrency constructs are widely used when developing complex software such as real-time, networking and multithreaded client–server applications. Consequently, testing a program, which includes concurrency constructs is a very elaborate and complex process. In this work, we first identify the different classes of synchronization anomalies that may occur in concurrent Java programs. We then consider testing concurrent Java programs against synchronization anomalies using dynamic data flow analysis techniques. Moreover, we show how the data flow analysis technique can be extended to detect such anomalies.     

Parallel mining of association rules

We consider the problem of mining association rules on a shared nothing multiprocessor. We present three algorithms that explore a spectrum of trade-offs between computation, communication, memory usage, synchronization, and the use of problem specific information. The best algorithm exhibits near perfect scaleup behavior, yet requires only minimal overhead compared to the current best serial algorithm     

On Exponential Synchronization of Kuramoto Oscillators

In this technical note we study the problem of exponential synchronization for one of the most popular models of coupled phase oscillators, the Kuramoto model. We consider the special case of finite oscillators with distinct, bounded natural frequencies. Our first result derives a lower bound on the coupling gain which is necessary for the onset of synchronization. This bound improves the one derived by Jadbabaie . We then calculate a lower bound on the coupling gain that is sufficient to guarantee oscillator synchronization and derive further sufficient conditions to ensure exponential synchronization of the angular frequencies of all oscillators to the mean natural frequency of the group. We also characterize the coupling gain that is sufficient for the oscillator phase differences to approach any desired compact set in finite time.      

Concentration of the Kirchhoff index for Erdős–Rényi graphs

Given an undirected graph, the resistance distance between two nodes is the resistance one would measure between these two nodes in an electrical network if edges were resistors. Summing these distances over all pairs of nodes yields the so-called Kirchhoff index of the graph, which measures its overall connectivity. In this work, we consider Erdős–Rényi random graphs. Since the graphs are random, their Kirchhoff indices are random variables. We give formulas for the expected value of the Kirchhoff index and show it concentrates around its expectation. We achieve this by studying the trace of the pseudoinverse of the Laplacian of Erdős–Rényi graphs. For synchronization (a class of estimation problems on graphs) our results imply that acquiring pairwise measurements uniformly at random is a good strategy, even if only a vanishing proportion of the measurements can be acquired.     

On the synchronized derivation depth of context-free grammars

We consider depth of derivations as a complexity measure for synchronized and ordinary context-free grammars. This measure differs from the earlier considered synchronization depth in that it counts the depth of the entire derivation tree. We consider (non-)existence of trade-offs when using synchronized grammars as opposed to non-synchronized grammars and establish lower bounds for certain classes of linear context-free languages.     

Recent advances in the analysis and control of large populations of neural oscillators

Many challenging problems that consider the analysis and control of neural brain rhythms have been motivated by the advent of deep brain stimulation as a therapeutic treatment for a wide variety of neurological disorders. In a computational setting, neural rhythms are often modeled using large populations of coupled, conductance-based neurons. Control of such models comes with a long list of challenges: the underlying dynamics are nonnegligibly nonlinear, high dimensional, and subject to noise; hardware and biological limitations place restrictive constraints on allowable inputs; direct measurement of system observables is generally limited; and the resulting systems are typically highly underactuated. In this review article, we highlight a collection of recent analysis techniques and control frameworks that have been developed to contend with these difficulties. Particular emphasis is placed on the problem of desynchronization for a population of pathologically synchronized neural oscillators, a problem that is motivated by applications to Parkinson’s disease where pathological synchronization is thought to contribute to the associated motor control symptoms. We also discuss other recent neural control applications that consider entrainment, phase randomization, synchronization, and clustering.