In the 3rd Annual acmsymposium 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...
详细信息
In the 3rd Annual acmsymposium 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.< >
The proceedings contain 110 papers. The topics discussed include: prediction capability of neural networks trained by Monte-Carlo paradigm;dynamic ID3: a symbolic learning algorithm for many-valued attribute domains;G...
ISBN:
(纸本)0897915674
The proceedings contain 110 papers. The topics discussed include: prediction capability of neural networks trained by Monte-Carlo paradigm;dynamic ID3: a symbolic learning algorithm for many-valued attribute domains;GnomeView: a tool for visual representation of human genome data;the VAIDAK medical image model reconstruction toolkit;distributed design of hip prostheses with BHAUTIK;the role of analogy in software reuse;integration of domain analysis and analogical approach for software reuse;object-oriented schema extension and abstraction;and method reuse in typed object-oriented languages.
The proceedings contain 8 papers. The topics discussed include: the software stack data-type as an operating system service;forth in space: interfacing SSBUV, a scientific instrument, to the space shuttle;first step t...
The proceedings contain 8 papers. The topics discussed include: the software stack data-type as an operating system service;forth in space: interfacing SSBUV, a scientific instrument, to the space shuttle;first step to forth engine construction;a forth course for engineers;a C-to-forth compiler;forth, meta Window, and GUI design;forth in mainstream computer science courses;and computer algebra in forth.
An algorithm is presented that abstracts out the "largest" common substructure of two given object-oriented class structures. This abstraction algorithm is based on two concepts: (1) a mathematical formulati...
详细信息
We present a methodology for the formal specification and development of software systems using Z and the refinement calculus. The methodology combines the data structuring capabilities and the codified discrete mathe...
详细信息
暂无评论