Chronolog is an extension of logic programming based on temporal logic. The paper presents a framework which can be used to exploit multiple levels of parallelism found in Chronolog programs, context parallelism, AND-...
详细信息
Chronolog is an extension of logic programming based on temporal logic. The paper presents a framework which can be used to exploit multiple levels of parallelism found in Chronolog programs, context parallelism, AND- and OR-parallelism. Based on an analysis of these modes of parallelism in Chronolog programs occurs when more than one child-computation are active at a time, and it is exploited through dynamic tagging approach typically used in dataflow computers. At the level of clause arguments, we introduce an intermediate virtual machine (CVM), which is granulated to exploit the argument parallelism through temporal unification. We also give the details of the CVM instruction set. The model is process-based and supports AND-, OR-parallelism in the highly distributed dataflow environment.
Currently, many parallel algorithms are defined for shared memory architectures. The preferred machine model is the PRAM, but this model does not take into account properties of existing architectures that have a dist...
详细信息
The shared memory paradigm offers a well known programming model for parallel systems. But it lacks from its bad performance in conventional implementations if it is used in large grain or page based systems. The main...
详细信息
ISBN:
(纸本)0780320182
The shared memory paradigm offers a well known programming model for parallel systems. But it lacks from its bad performance in conventional implementations if it is used in large grain or page based systems. The main problems are (1) the transparent view on the system level, (2) the false sharing caused by locating several consistency units into the same transportation unit, and that (3) high level software implementations are not integrated within the system architecture. The first point is addressed by annotating programming objects and deriving a specific configuration of system functionalities. The second point is solved by Game, the General and Autonomous Merging Environment which allows a multiple reader, multiple writer approach. The third point is directed by three implementation models of Game. A hardware based implementation and even a software based implementation are able to hide the costs of the local activities to perform Game by the network latency.
The paper focuses on the problem of the multi-spectral image segmentation, which leads - through the data fusion of several mono-spectral images - to reliable and robust vision systems for military or industrial purpo...
详细信息
The paper focuses on the problem of the multi-spectral image segmentation, which leads - through the data fusion of several mono-spectral images - to reliable and robust vision systems for military or industrial purposes. The proposed approach does not fit the classical taxinomy of image data fusion methods: indeed, data fusion is performed during the segmentation, in parallel, of different images. The presented algorithm has been implemented on the Connection Machine CM5 with the data programming style.
One of the difficulties of parallelprogramming is the gap between the desire of programmers to describe computations with manageable abstractions and the detailed description of parallelism, communication and synchro...
详细信息
Combinational logic synthesis is a very important but computationally expensive phase of VLSI system design. parallel processing offers an attractive solution to reduce this design cycle time. In this paper, we descri...
详细信息
Combinational logic synthesis is a very important but computationally expensive phase of VLSI system design. parallel processing offers an attractive solution to reduce this design cycle time. In this paper, we describe ProperMIS, a portable parallel algorithm for logic synthesis based on the MIS multi-level logic synthesis system. As part of this work, we have developed novel parallel algorithms for the different logic transformations of the MIS system. Our algorithm uses an asynchronous message-driven computing model with no synchronizing barriers separating phases of parallel computation. The algorithm is portable across a wide variety of parallelarchitectures, and is built around a well-defined sequential algorithm interface, so that we can benefit from future expansion of the sequential algorithm. We present results on several MCNC and ISCAS benchmark circuits for a variety of shared memory and distributed processing architectures. Our implementation produces speedups of an average of 4 on 8 processors.
作者：
PHILIPPSEN, MICSI
International Computer Science Institute Berkeley CA and Dept. of Informatics University of Karlsruhe
This paper investigates the problem of aligning array data and processes in a distributed-memory implementation. We present complete algorithms for compile-time analysis, the necessary program restructuring, and subse...
详细信息
ISBN:
(纸本)9780897917001
This paper investigates the problem of aligning array data and processes in a distributed-memory implementation. We present complete algorithms for compile-time analysis, the necessary program restructuring, and subsequent code-generation, and discuss their complexity. We finally evaluate the practical usefulness by quantitative experiments. The technique presented analyzes complete programs, including branches, loops, and nested parallelism. Alignment is determined with respect to offset, stride, and general ass's relations. Pplacement of both data and processes are computed in a unifying framework based on an extended preference graph and its analysis. Dynamic redistributions are derived. The experimental results are very encouraging. The optimization algorithms implemented in our Modula-2* compiler improved the execution times of the programs by an average over 40% on a MasPar MP-1 with 16384 processors.
We describe the design of a compilation system, which translates Fortran programs automatically into explicitly parallel programs for a massively parallel architecture. Such a compiler must automatically generate data...
详细信息
This paper focuses on the problem of the massively parallel implementation of image processing algorithms. In previous theoretical studies the parallel software requirements to implement image processing algorithms we...
详细信息
ISBN:
(纸本)0819419230
This paper focuses on the problem of the massively parallel implementation of image processing algorithms. In previous theoretical studies the parallel software requirements to implement image processing algorithms were pointed out. A test algorithm, which is representative enough of the requirements for edge and region segmentations was chosen. Our goal here is to detail its implementation. The proposed test algorithm was implemented with the data programming model, on the connection machine CM5 in C*, which is an extension of the C programming language. The crux points of the parallel implementation are underlined. Edge point detection requires only parallel operations, and regular communications. Conversely, region extraction and edge chaining require irregular communications, therefore for a better efficiency, in both cases, the original algorithms were modified. These studies are in relation with the problem of finding tools and methods to compare and to evaluate parallelarchitectures. One of the two proposed algorithms is deduced of this one.
We have developed a programming template to implement divide-and-conquer algorithms on MIMD computers. The template is based on the parallel Divide-and-Conquer function of Mou and Hudak. We explore the programmability...
详细信息
We have developed a programming template to implement divide-and-conquer algorithms on MIMD computers. The template is based on the parallel Divide-and-Conquer function of Mou and Hudak. We explore the programmability and performance of this approach by solving some well-known numerical problems on a shared-memory multiprocessor and a multi-computer. A by-product of this work is a new parallel algorithm for solving tridiagonal systems of equations.
暂无评论