On loop transformations for generalized cycle shrinking

This paper describes several loop transformation techniques for extracting parallelism from nested loop structures. Nested loops can then be scheduled to run in parallel so that execution time is minimized. One technique is called selective cycle shrinking, and the other is called true dependence cycle shrinking. It is shown how selective shrinking is related to linear scheduling of nested loops and how true dependence shrinking is related to conflict-free mappings of higher dimensional algorithms into lower dimensional processor arrays. Methods are proposed in this paper to find the selective and true dependence shrinkings with minimum total execution time by applying the techniques of finding optimal linear schedules and optimal and conflict-free mappings proposed by W. Shang and A.B. Fortes     

Scheduling DAG's for asynchronous multiprocessor execution

A new approach is given for scheduling a sequential instruction stream for execution “in parallel” on asynchronous multiprocessors. The key idea in our approach is to exploit the fine grained parallelism present in the instruction stream. In this context, schedules are constructed by a careful balancing of execution and communication costs at the level of individual instructions, and their data dependencies. Three methods are used to evaluate our approach. First, several existing methods are extended to the fine grained situation. Our approach is then compared to these methods using both static schedule length analyses, and simulated executions of the scheduled code. In each instance, our method is found to provide significantly shorter schedules. Second, by varying parameters such as the speed of the instruction set, and the speed/parallelism in the interconnection structure, simulation techniques are used to examine the effects of various architectural considerations on the executions of the schedules. These results show that our approach provides significant speedups in a wide-range of situations. Third, schedules produced by our approach are executed on a two-processor Data General shared memory multiprocessor system. These experiments show that there is a strong correlation between our simulation results, and these actual executions, and thereby serve to validate the simulation studies. Together, our results establish that fine grained parallelism can be exploited in a substantial manner when scheduling a sequential instruction stream for execution “in parallel” on asynchronous multiprocessors     

On the performance of synchronized programs in distributed networkswith random processing times and transmission delays

A synchronizer is a compiler that transforms a program designed to run in a synchronous network into a program that runs in an asynchronous network. The behavior of a simple synchronizer, which also represents a basic mechanism for distributed computing and for the analysis of marked graphs, was studied by S. Even and S. Rajsbaum (1990) under the assumption that message transmission delays and processing times are constant. We study the behavior of the simple synchronizer when processing times and transmission delays are random. The main performance measure is the rate of a network, i.e., the average number of computational steps executed by a processor in the network per unit time. We analyze the effect of the topology and the probability distributions of the random variables on the behavior of the network. For random variables with exponential distribution, we provide tight (i.e., attainable) bounds and study the effect of a bottleneck processor on the rate     

E-kernel: an embedding kernel on the IBM victor V256 multiprocessorfor program mapping and network reconfiguration

We present the design of E-kernel, an embedding kernel on the Victor V256 message-passing partitionable multiprocessor, developed for the support of program mapping and network reconfiguration. E-kernel supports the embedding of a new network topology onto Victor's 2D mesh and also the embedding of a task graph onto the 2D mesh network or the reconfigured network. In the current implementation, the reconfigured network can be a line or an even-size ring, and the task graphs meshes or tori of a variety of dimensions and shapes or graphs with similar topologies. For application programs having these task graph topologies and that are designed according to the communication model of E-kernel, they can be run without any change on partitions connected by the 2D mesh, line, or ring. Further, E-kernel attempts the communication optimization of these programs on the different networks automatically, thus making both the network topology and the communication optimization attempt completely transparent to the application programs. Many of the embeddings used in E-kernel are optimal or asymptotically optimal (with respect to minimum dilation cost). The implementation of E-kernel translated some of the many theoretical results in graph embeddings into practical tools for program mapping and network reconfiguration in a parallel system. E-kernel is functional on Victor V256. Measurements of E-kernel's performance on V256 are also included     

On the design of dynamic associative neural memories

We consider the design problem for a class of discrete-time and continuous-time neural networks. We obtain a characterization of all connection weights that store a given set of vectors into the network, that is, each given vector becomes an equilibrium point of the network. We also give sufficient conditions that guarantee the asymptotic stability of these equilibrium points.     

Using recurrent neural networks for adaptive communication channelequalization

Nonlinear adaptive filters based on a variety of neural network models have been used successfully for system identification and noise-cancellation in a wide class of applications. An important problem in data communications is that of channel equalization, i.e., the removal of interferences introduced by linear or nonlinear message corrupting mechanisms, so that the originally transmitted symbols can be recovered correctly at the receiver. In this paper we introduce an adaptive recurrent neural network (RNN) based equalizer whose small size and high performance makes it suitable for high-speed channel equalization. We propose RNN based structures for both trained adaptation and blind equalization, and we evaluate their performance via extensive simulations for a variety of signal modulations and communication channel models. It is shown that the RNN equalizers have comparable performance with traditional linear filter based equalizers when the channel interferences are relatively mild, and that they outperform them by several orders of magnitude when either the channel's transfer function has spectral nulls or severe nonlinear distortion is present. In addition, the small-size RNN equalizers, being essentially generalized IIR filters, are shown to outperform multilayer perceptron equalizers of larger computational complexity in linear and nonlinear channel equalization cases.     

Quantitative feedback theory with applications in welding

Two different control systems were developed using quantitative feedback theory for weld quality improvement. The first application to be discussed was designed for the resistance pinch welding process and uses electrode displacement and force as feedback parameters. A correlation between weld quality and electrode displacement is established for constant electrode force. The system is capable of producing repeatable welds of consistent quality, with wide variations in weld parameters. This is the first time feedback control has been successfully applied to pinch welding. The second example presented in this paper was developed for penetration control of the gas-tungsten-arc welding process. The feedback signal is obtained by measuring the amount of light emitted from the back side of the weld. Welds of constant penetration have been demonstrated in tests with travel speeds varying from 1.5 to 6 inches per minute and with 200 per cent changes in part thickness.     

Multi-input,multi-output flight control system design for the YF-16 using nonlinear QFT and pilot compensation

Nonlinear quantitative feedback theory (QFT) and pilot compensation techniques are used to design a 2 × 2 flight control system for the YF-16 aircraft over a large range of plant uncertainty. The design is based on numerical input-output time histories generated with a FORTRAN implemented nonlinear simulation of the YF-16. The first step of the design process is the generation of a set of equivalent linear time-invariant (LTI) plant models to represent the actual nonlinear plant. It has been proven that the solution to the equivalent plant problem is guaranteed to solve the original nonlinear problem. Standard QFT techniques are then used in the design synthesis based on the equivalent plant models. A detailed mathematical development of the method used to develop these equivalent LTI plant models is provided. After this inner-loop design, pilot compensation is developed to reduce the pilot's workload. This outer-loop design is also based on a set of equivalent LTI plant models. This is accomplished by modelling the pilot with parameters that result in good handling qualities ratings, and developing the necessary compensation to force the desired system responses.