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     

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.     

UTEC and Ferut: the University of Toronto's computation centre

Although not well known, the University of Toronto had a very early computer-development program and in 1952 was one of the first few institutions with an operable computer in North America. This article describes the university's initial attempt to build the UTEC computer and how it acquired the pioneering Ferut machine     

Nonlocal quasi-Newton method for solving convex variational inequalities

Conclusion In the optimization problem [f ₀(x)│h_i(x)<-0,i=1,…,l] relaxation of the functionf ₀(x)+Nh⁺(x) does not produce, as we know [6, 7], α_k=1 in Newton's method with the auxiliary problem (5), (6), whereF(x)=f _0′(x). For this reason, Newton type methods based on relaxation off ₀(x)+Nh⁺(x) are not superlinearly convergent (so-called Maratos effect). The results of this article indicate that if (F(x)=f _0′(x), then replacement of the initial optimization problem with a larger equivalent problem (7) eliminates the Maratos effect in the proposed quasi-Newton method. This result is mainly of theoretical interest, because Newton type optimization methods in the space of the variablesx ∈R ⁿ are less complex. However to the best of our knowledge, the difficulties with nonlocal convergence arising in these methods (choice of parameters, etc.) have not been fully resolved [10, 11]. The discussion of these difficulties and comparison with the proposed method fall outside the scope of the present article, which focuses on solution of variational inequalities (1), (2) for the general caseF′(x)≠F′ ^T(x). Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 78–91, November–December, 1994.     

First break refraction event picking using fuzzy logic systems

First break picking is a pattern recognition problem in seismic signal processing, one that requires much human effort and is difficult to automate. The authors' goal is to reduce the manual effort in the picking process and accurately perform the picking. Feedforward neural network first break pickers have been developed using backpropagation training algorithms applied either to an encoded version of the raw data or to derived seismic attributes which are extracted from the raw data. The authors summarize a study in which they applied a backpropagation fuzzy logic system (BPFLS) to first break picking. The authors use derived seismic attributes as features, and take lateral variations into account by using the distance to a piecewise linear guiding function as a new feature. Experimental results indicate that the BPFLS achieves about the same picking accuracy as a feedforward neural network that is also trained using a backpropagation algorithm; however, the BPFLS is trained in a much shorter time, because there is a systematic way in which the initial parameters of the BPFLS can be chosen, versus the random way in which the weights of the neural network are chosen     

Robotica: a Mathematica package for robot analysis

Robotica is a computer aided design package for robotic manipulators developed in the Coordinated Science Laboratory at the University of Illinois at Urbana-Champaign. It encapsulates over 30 functions into a Mathematica package allowing efficient symbolic and numeric calculation of kinematic and dynamic equations for multi-degree-of-freedom manipulators. An X-Windows front end that utilizes the interprocess communication features of Mathematica 2.1 has also been created for ease of use. This paper describes the most important features of the package and how they are used