The paper considerably extends the multiprocessor scheduling techniques of G.N.S. Prasanna and B.R. Musicus (1995; 1991) and applies it to matrix arithmetic compilation. Using optimal control theory in the special case where the speedup function of each task is p/sup /spl alpha// (where p is the amount of processing power applied to the task), closed form solution for task graphs formed from parallel and series connections was derived by G.N.S. Prasanna and B.R. Musicus (1995; 1991). The paper extends these results for arbitrary DAGS. The optimality conditions impose nonlinear constraints on the flow of processing power from predecessors to successors, and on the finishing times of siblings. The paper presents a fast algorithm for determining and solving these nonlinear equations. The algorithm utilizes the structure of the finishing time equations to efficiently run a conjugate gradient minimization, leading to the optimal solution. The algorithm has been tested on a variety of DAGs commonly encountered in matrix arithmetic. The results show that if the p/sup /spl alpha// speedup assumption holds, the schedules produced are superior to heuristic approaches. The algorithm has been applied to compiling matrix arithmetic (K.P. Belkhale and P. Banerjee, 1993), for the MIT Alewife machine, a distributed shared memory multiprocessor. While matrix arithmetic tasks do not exactly satisfy the p/sup /spl alpha// speedup assumptions, the algorithm can be applied as a good heuristic. The results show that the schedules produced by our algorithm are faster than alternative heuristic techniques.

In the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 216-228 (JuIy 1991), we presented several new results in the theory of homogeneous multiprocessor scheduling. A directed acyclic graph (DAG) of tasks was to be scheduled. Tasks were assumed to be parallelizable-as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization and task scheduling overheads, this speedup increases less than linearly with the number of processors applied. The optimal scheduling problem is to determine the number of processors assigned to each task, and to the task sequencing, to minimise the finishing time. Using optimal control theory, in the special case where the speedup function of each task is p/sup /spl alpha// (where p is the amount of processing power applied to the task), a closed form solution for task graphs formed from parallel and series connections was derived. This paper considerably extends these techniques for arbitrary DAGs and applies them to matrix arithmetic compilation. The optimality conditions impose nonlinear constraints on the flow of processing power from predecessors to successors, and on the finishing times of siblings. This paper presents a fast algorithm for determining and solving these nonlinear equations. The algorithm utilizes the structure of the finishing time equations to efficiently run a conjugate gradient minimization leading to the optimal solution. The algorithm has been tested on a variety of DAGs. The results presented show that it is superior to alternative heuristic approaches.>

This paper presents a hierarchical approach for compiling macro dataflow graphs for multiprocessors with local memory. Macro dataflow graphs comprise several nodes (or macro operations) that must be executed subject to prespecified precedence constraints. Programs consisting of multiple nested loops, where the precedence constraints between the loops are known, can be viewed as macro dataflow graphs. The hierarchical compilation approach comprises a processor allocation phase followed by a partitioning phase. In the processor allocation phase, using estimated speedup functions for the macro nodes, computationally efficient techniques establish the sequencing and parallelism of macro operations for close-to-optimal run-times. The second phase partitions the computations in each macro node to maximize communication locality for the level of parallelism determined by the processor allocation phase. The same approach can also be used for programs consisting of multiple loop nests, when each of the nested loops can be characterized by a speedup function. These ideas have been implemented in a prototype structure-driven compiler, SDC, for expressions of matrix operations. The paper presents the performance of the compiler for several matrix expressions on a simulator of the Alewife multiprocessor.>

A general technique for protecting computation with systematic-separate codes is presented. These codes use parity symbols to check the result of computation. A group-theoretic approach and model computation are used as operations in an algebraic group. It is shown that in order for a code to commute with computation, it must define a homomorphism between the original group and the group of parity symbols. A quotient group isomorphism is applied, and the problem of finding coding schemes is reduced to that of finding normal subgroups. In many instances, the method can be shown to identify all possible systematic-separate codes. For a given code, conditions on errors are given so that they may be detected and corrected. The extension of the technique to other algebraic systems is discussed, and two examples are included.>

An extension of Rife's discrete Fourier transform (DFT) interpolation into a complex form is presented. The method has several advantages over Rife's original formula. It can estimate the decay rate of the input sequence as well as the frequency, and does not require a square-root operation. An error analysis suggests a powerful but simple refinement step which can nearly attain the Cramer-Rao (CR) bound. An interpolation formula is derived, and its iteration into a refinement procedure is discussed. The procedure also allows the use of arbitrary windows to suppress the interference of other frequency components in the data that are typically found with real and/or damped sequences.>

Article Generalised multiprocessor scheduling using optimal control Share on Authors: G. N. Srinivasa Prasanna Laboratory for Computer Science and Research Laboratory for Electronics, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science and Research Laboratory for Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile , Bruce R. Musicus Laboratory for Computer Science and Research Laboratory for Electronics, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science and Research Laboratory for Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 216–228https://doi.org/10.1145/113379.113399Published:01 June 1991 18citation374DownloadsMetricsTotal Citations18Total Downloads374Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors describe a hardware prototype of a fault-tolerant parallel digital signal processor (DSP) that uses the single fault correction scheme of B.E. Musicus and W. S. Song (1987, 1990). Ten of the sixteen DSP-32 C processors perform identical linear operations on ten different data streams (a complex fast Fourier transform (FFT) for a sonar beamforming application), three do arithmetic checksums on the input data and FFTs on these checksums and one generates the syndromes and does fault detection and correction using a generalized likelihood ratio test (GLRT). A faulty output from one of the first 13 processors can be detected and corrected without having to recalculate that output. The prototype is not itself fault-tolerant, but is intended to benchmark applications and to quantify the actual overheads involved in executing the fault-tolerance algorithm.>

A robust A/D converter system is described which requires much less hardware overhead than traditional modular redundancy approaches. A modest amount of oversampling is used to generate information which can be exploited to achieve fault tolerance. A generalized likelihood ratio test is used to detect the most likely failure and also to estimate the optimum signal reconstruction. The error detection and correction algorithm reduces to a simple form and requires only a slight amount of hardware overhead. A derivation of the algorithm is followed by simulation results.>

In recent publication, S. Kay (1988) described a method of estimating the frequency of a complex exponential from noisy samples of the time waveform. The method is attractive because of its computational simplicity, because it is based on phase differences (which may already be available at no cost in some systems), and because its performance attains the Cramer-Rao bound at high SNR. The authors present a novel derivation of Kay's method, extend it to the estimation of the parameters of linear FM chirps and of multiple signals, provide an adaptive version of the algorithm, and provide an explanation for the threshold behavior of phase difference methods.>

This paper explores line labeling algorithms for extracting the mask layers from an optical image of a VLSI chip. We first create a suitable world model for VLSI images. Next, we introduce representation schemes for object features, together with the natural constraints these features satisfy. This label set is an extension of Huffman, Clowes, and Kanade's label sets. Finally, we show how to interpret VLSI scenes by using a constrained labeling strategy. Performance of our labeling algorithms is demonstrated on some simple but representative simulated images of CMOS logic gates.

We describe a new Maximum Entropy pole-zero spectral estimation method. The model is designed to match given correlation and cepstral values, yet achieve the maximum possible entropy. The solution is based on solving a generalized symmetric almost-Toeplitz eigenvalue problem. We characterize this solution, present a fast computational algorithm, and give examples.

We suggest an alternative interpretation of Frieden's results which better explains the relationship between Maximum Entropy, Maximum A Posteriori, and Minimum Mean-Square Error estimation in his dice problem.

A new method is presented for estimating the power spectral density matrix for multichannel data, given correlation values for linear combinations of the channels and given an initial estimate of the spectral density matrix. A derivation of the method from the relative-entropy principle is given. The results differ significantly from the Multisignal Relative-Entropy ("Minimum-Cross-Entropy") Spectrum Analysis of Johnson and Shore because the present method does not arbitrarily force the final distributions of the various channels to be independent. For the special case when correlation values are given only for the sum of the channels, Multichannel Relative-Entropy Spectrum Analysis is shown to reduce to a two-stage procedure: first a smooth power-spectrum model is fitted to the correlations of the sum; then final estimates of the spectra and cross spectra are obtained through linear filtering. Illustrative numerical examples are presented.

We present a new approach to the problem of estimating multiple signal and parameter unknowns given noisy and incomplete data. Using cross-entropy, we fit a separable density to the given model density, then use this separable density to estimate each unknown independently. Not only does this method include all the various MAP methods as degenerate cases, but it also directly leads to a simple iterative algorithm which can solve either the cross-entropy method or any of the MAP methods. This algorithm is particularly effective for exponential families of densities. Applications include estimation using grouped or quantized data, and a wide variety of reconstruction, smoothing, interpolation, extrapolation and modeling problems involving linear Gaussian systems.

While the covariance and modified covariance methods of linear prediction have many desirable properties for spectral estimation, they are not guaranteed to yield stable model estimates. In this paper we present a simple iterative method for finding the best stable solution to the covariance or modified covariance problems. The technique alternates between a data extrapolation step and calculating an "infinite interval" covariance method estimate. Each iteration reduces the prediction error and thus improves the parameter estimates. Furthermore, convergence can be guaranteed to either the solution to the original covariance problem (if it is stable), or else to a set of polynomials with one or more zeroes on the unit circle and the rest inside. Several examples are shown comparing the iterative methods with the unconstrained covariance and modified covariance methods, and with Burg's algorithm.

For most signal models of interest, Maximum Likelihood (ML) parameter estimation in the presence of noise is a difficult, non-linear problem. A new iterative algorithm has been developed for ML estimation, however, which effectively decouples the uncertainty in the signal and parameter values, thus simplifying the calculation required. It can be shown that the likelihood function increases on each iteration of the algorithm. When applied to a particular pole-zero (ARMA) signal model, each pass consists of a linear smoothing filter followed by solving a set of linear equations for both the pole and zero polynomial coefficients.