The paper presents a new specification style for computations to be executed in an essentially multiprocessor environment. This style is based on two pragmatic premises: (1) the specification is derived from considera...
详细信息
The paper presents a new specification style for computations to be executed in an essentially multiprocessor environment. This style is based on two pragmatic premises: (1) the specification is derived from considerations of system reaction related to system state, rather than to a goal to be achieved, (2) a reaction enabled by a system state is executed independently of any other system activity but its outcome is accepted only if the system “by itself” satisfies a postguard condition, i.e. finds itself in a (possibly different) well-defined st
This paper provides a unifying mathematical proof which replaces a mechanical certification of the optimal parallelization of sorting networks on a case basis. Parallelization of sequential program traces by means of ...
详细信息
This paper provides a unifying mathematical proof which replaces a mechanical certification of the optimal parallelization of sorting networks on a case basis. Parallelization of sequential program traces by means of semantic-preserving transformation is discussed in the literature in the context of a method for synthesis of systolic architecture. The issue of optimal parallelization is important in systolic design. The mathematical proof provides a better insight into the fundamental aspects of the transformation.
In this paper the concept for a software environment for developing engineering application systems for multiprocessor hardware (MIMD) is presented. The philosophy employed is to solve the largest problems possible in...
详细信息
In this paper the concept for a software environment for developing engineering application systems for multiprocessor hardware (MIMD) is presented. The philosophy employed is to solve the largest problems possible in a reasonable amount of time, rather than solve existing problems faster. In the proposed environment most of the problems concerning parallel computation and handling of large distributed data spaces are hidden from the application program developer, thereby facilitating the development of large-scale software applications. Applications developed under the environment can be executed on a variety of MIMD hardware; it protects the application software from the effects of a rapidly changing MIMD hardware technology.
This paper exposes the concurrent characteristic in the communication between processors in a transputer based system, and proposes an approximate formula for assessing the granularity of distributing the parallel pro...
详细信息
This paper exposes the concurrent characteristic in the communication between processors in a transputer based system, and proposes an approximate formula for assessing the granularity of distributing the parallel processes among processors. The really measured results for a pipeline sorting program running on the T-rack confirm these deduced results.
We present a simple and uniform transformational system for extracting parallelism from programs. The transformations are studied as a formal system. We define a measure of program improvement, and show that the trans...
详细信息
We present a simple and uniform transformational system for extracting parallelism from programs. The transformations are studied as a formal system. We define a measure of program improvement, and show that the transformations improve programs with respect to the measure. We show that it is possible to compute limits of infinite sequences of the transformations; this allows our system to implement software pipelining, and leads to a general solution to the problem of software pipelining in the presence of tests. Using the primitive transformations and the limit-taking transformation, it is possible to express the classical parallelization techniques for vector, multiprocessor, and VLIW machines. Thus, our transformational system can be viewed as a formal foundation for the area of parallelization. We present implementations of two techniques, doacross and a simple form of vectorization.
The use of Petri nets for defining a general static analysis framework for Ada tasking is advocated. The framework has evolved into a collection of tools that have proven to be a very valuable platform for experimenta...
详细信息
The use of Petri nets for defining a general static analysis framework for Ada tasking is advocated. The framework has evolved into a collection of tools that have proven to be a very valuable platform for experimental research. The design and implementation of tools that make up the tasking-oriented toolkit for the Ada language (TOTAL) are defined and discussed. Modeling and query/analysis methods and tools are discussed. Example Ada tasking programs are used to demonstrate the utility of each tool individually as well as the way the tools integrate. TOTAL is divided into two major subsytems, the front-end translator subsystem (FETS) and the back-end information display subsystem (BIDS). Three component tools that make up FETS are defined. Examples demonstrate the way these tools integrate in order to perform the translation of Ada source to Petri-net format. The BIDS subsystem and, in particular, the use of tools and techniques to support user-directed, but transparent, searches of Ada-net reachability graphs are discussed.
Two sorting algorithms are described, general_cycle_sort, and special_cycle_sort, based upon the decomposability of a permutationinto a product of cyclic permutations. Under the conditions in which these algorithms ar...
详细信息
Two sorting algorithms are described, general_cycle_sort, and special_cycle_sort, based upon the decomposability of a permutationinto a product of cyclic permutations. Under the conditions in which these algorithms are applicable, the sorting can be accomplishedin linear *** May 1987. revised April 1990.
Most sorting algorithms for linearly connected and mesh-connected parallel computers have been developed assuming that the number of processors equals the number of elements to be sorted. This assumption has simplifie...
详细信息
Most sorting algorithms for linearly connected and mesh-connected parallel computers have been developed assuming that the number of processors equals the number of elements to be sorted. This assumption has simplified analysis of the problem, however, it causes unnecessary communication costs because elements must be permuted across large numbers of processors. It also underutilizes processors because comparison operations involve two data elements for each processor. By modifying parallel sorting algorithms to use fewer processors, we are able to improve processor utilization and decrease communication costs. This leads to constant factor improvements in the best parallel sorting bounds for both mesh-connected and linearly connected SIMD parallel computers. (Previous bounds are within a constant factor of optimal.)
The LADY programming environment has been developed to support the design, implementation, testing, debugging and monitoring of distributed systems with special focus on operating systems. This paper describes the str...
详细信息
The LADY programming environment has been developed to support the design, implementation, testing, debugging and monitoring of distributed systems with special focus on operating systems. This paper describes the structuring model of the system implementation language LADY. In LADY, a distributed system is viewed as a collection of cooperating objects connected through typed interfaces. The language offers dynamic modifications of the program structure such as generation and deletion of objects and their interconnections as well as migration and checkpointing of objects. Further features include the extensibility of programs and recursive definition of objects. The structuring facilities of LADY are demonstrated by an example and experiences with the language are discussed.
In this paper, we describe ASPEN, a concurrent stream processing environment. ASPEN is novel in that it provides a programming model in which programmers use simple annotations to exploit varying degrees and types of ...
详细信息
In this paper, we describe ASPEN, a concurrent stream processing environment. ASPEN is novel in that it provides a programming model in which programmers use simple annotations to exploit varying degrees and types of concurrency. The degree of concurrency to be exploited is not fixed by the program specification or by the underlying system. Increasing or decreasing the degree of concurrency to be exploited during execution does not require rewriting the entire program, but rather, simply reannotating it. Examples are given to illustrate the varying types of concurrency inherent in programs written within the stream processing paradigm. We show how programs may be annotated to exploit these varying degrees of concurrency. We briefly describe our implementation of ASPEN.
暂无评论