The article develops a framework for message-passing architectures consisting of a machine model called communicating random access machine (CRAM) and a programming paradigm. The CRAM model serves as a vehicle for the...
详细信息
The article develops a framework for message-passing architectures consisting of a machine model called communicating random access machine (CRAM) and a programming paradigm. The CRAM model serves as a vehicle for the design and analysis of message-passing algorithms. The message-passing paradigm makes the mapping of algorithms that fit this paradigm onto message-passing architectures more natural.< >
MOVIE (Multitasking Object-oriented Visual Interactive Environment) is the new software system for High Performance Distributed Computing (HPDC), currently in the advanced design and implementation stage at Northeast ...
详细信息
In practice, it is interesting to map n-dimensional algorithms, or algorithms with n nested loops, onto (k-1)-dimensional arrays where k<n. For example, many algorithms at bit level are at least 4-dimensional (matr...
详细信息
ISBN:
(纸本)0818626720
In practice, it is interesting to map n-dimensional algorithms, or algorithms with n nested loops, onto (k-1)-dimensional arrays where k algorithms at bit level are at least 4-dimensional (matrix multiplication, convolution, LU decomposition, etc.) and most existing bit level processor arrays are 2-dimensional. A computational conflict occurs if two or more computations of an algorithm are mapped into the same processor and the same execution time. In this paper, some open problems in the previous work are considered. A procedure is proposed to test if or not a given mapping has computational conflicts and a lower bound on the total execution time is provided. Based on the testing procedure and the lower bound, the complexity and the optimality of the optimization procedure in [17] is improved. The integer programming formulation is also discussed and used to find the optimal time mapping for the 5-dimensional bit level matrix multiplication algorithm into a 2-dimensional bit level processor array.
The proceedings contain 24 papers. The special focus in this conference is on parallel Image Analysis. The topics include: From equations to hardware: towards systematic mapping of algorithms onto parallel architectur...
ISBN:
(纸本)9783540563464
The proceedings contain 24 papers. The special focus in this conference is on parallel Image Analysis. The topics include: From equations to hardware: towards systematic mapping of algorithms onto parallelarchitectures;visual pattern recognition with neural networks.;object recognition by a self-organizing neural network which grows adaptively (abstract);intelligent pattern recognition and applications (summary);path-controlled graph grammars for syntactic pattern recognition;describing objects by a multi-resolution syntactic approach;parallel manipulations of octrees and quadtrees;vision reflex operators;note on two-dimensional pattern matching by optimal parallel algorithms;an efficient line drawing algorithm for parallel machines;a characterization of recognizable picture languages;constant leaf-size hierarchy of two-dimensional altemsfing turing machines;shape recovery and error correction based on hypothetical constraints by parallel network for energy minimization;use of gradated patterns in an associative neural memory for invariant pattern recognition;context-sensitivity of puzzle grammars;parallel generation and parsing of array languages using reversible cellular automata;parallel recognition of multidimensional images using regular tree grammars;optimal parallel algorithms for multidimensional image template matching and pattern matching;learning of recognizable picture languages;circular DNA and splicing systems;learning even equal matrix languages based on control sets;parallel dynamic programming algorithms for image recognition based on its contour;neural model for pattern recognition;three-dimensional sequential/parallel universal array grammars and object pattern analysis.
The proceedings contain 33 papers. The special focus in this conference is on parallel Computation. The topics include: Scalable cache coherence for shared memory multiprocessors;new program restructuring technology;d...
ISBN:
(纸本)9783540554370
The proceedings contain 33 papers. The special focus in this conference is on parallel Computation. The topics include: Scalable cache coherence for shared memory multiprocessors;new program restructuring technology;data parallel program design;a powerful high-level debugger for parallel programs;the PCP/PFP programming models on the BBN TC2000;knowledge-based parallelization for distributed memory systems;parallelization for multiprocessors with memory hierarchies;data structures for optimizing programs with explicit parallelism;MODULA-S: a language to exploit two dimensional parallelism;ADAPTing fortran 90 array programs for distributed memory architectures;evolution of massive parallel compute servers from a research object to a production pool;processor scheduling in multiprocessor systems;multipacket routing on rings;massively parallel processing in high energy physics: the CERN-MPPC project;a heuristic algorithm for dynamic task allocation in highly parallel systems;analysis of parallel lisp programs based on a trace mechanism;a distributed implementation of flat concurrent prolog on multi-transputer environments;negation in conclog;symbolic computation and parallel software;on the parallelization of characteristic-set-based algorithms;multiplication as parallel as possible;on the existence of an efficient parallel algorithm for a graph theoretic problem;on the multi-threaded computation of modular polynomial greatest common divisors;a buchberger algorithm for distributed memory multiprocessors;computational biology on massively parallel machines;time-parallel multigrid in an extrapolation method for time-dependent partial differential equations;parallelization of simulation tasks: methodology - implementation -application;parallel algorithms for stress analysis on shared-memory multiprocessors and elastic load-balancing for image processing algorithms.
This paper explores the use of Proteus, an architecture-independent language suitable for prototyping parallel and distributed programs. Proteus is a high-level imperative notation based on sets and sequences with a s...
详细信息
This paper explores the use of Proteus, an architecture-independent language suitable for prototyping parallel and distributed programs. Proteus is a high-level imperative notation based on sets and sequences with a single construct for the parallel composition of processes communicating through shared memory. Several different parallel algorithms for N-body simulation are presented in Proteus, illustrating how Proteus provides a common foundation for expressing the various parallelprogramming models. This common foundation allows prototype parallel programs to be tested and evolved without the use of machine-specific languages. To transform prototypes to implementations on specific architectures, program refinement techniques are utilized. Refinement strategies are illustrated that target broad-spectrum parallel intermediate languages, and their viability is demonstrated by refining an N-body algorithm to data-parallel CVL code.< >
Adapt is a data parallel little language for both local and global image processing on parallel computers. It is architecture independent: it hides the distribution of data, the number of processors and their topology...
详细信息
ISBN:
(纸本)0819408131
Adapt is a data parallel little language for both local and global image processing on parallel computers. It is architecture independent: it hides the distribution of data, the number of processors and their topology, and even the existence of multiple processes from the programmer. The programs Adapt generates are efficient, even as compared with hand code, are easy to compile for MIMD architectures, and are easy to write. Adapt presents the programmer with three underlying concepts: the idea of the split and merge programming model, raster order per-pixel processing, and the scanline/transpose method. These three concepts make it possible to implement a wide variety of image processing algorithms, including histogram, uniform convolution, run-length encoding, image warping, connected components analysis, and two-dimensional fast Fourier transform. Performance of Adapt on Sun/Unix workstations, the Carnegie Mellon Warp machine, and the Carnegie Mellon - Intel Corporation iWarp computer will be presented. Adapt is being used in an implementation of the emerging ISO/ANSI standard Programmer's Imaging Kernel System. The implementation strategy of the library will be discussed.
A dual-level dynamic load distribution strategy is proposed for allocating parallel computations with unpredictable structures to hypercube based distributed systems. Computations with dynamic structures represent a w...
详细信息
By exploiting the structure of a directed toroidal graph, the authors have developed a parallel solution to find the shortest path. A parallel dynamic programming solution to finding the minimum cost path is presented...
详细信息
By exploiting the structure of a directed toroidal graph, the authors have developed a parallel solution to find the shortest path. A parallel dynamic programming solution to finding the minimum cost path is presented. First the authors map the toroidal graph to a planar graph, whose structure is exploited to form a parallel algorithm suitable for a message-passing parallel architecture. The problem has applications in surface reconstruction, where contours of a surface are represented as graphs. Finding the shortest-path in these graphs corresponds to finding a best-fit surface over the contours. By parallelizing the solution, the authors have obtained a significant speedup to a computationally intensive problem. Since generic message passing is used for interprocessor communication, the proposed algorithm can be implemented in any distributed or parallel environment. In a heterogeneous environment, relative processor speed and memory would have to be considered for load balancing.< >
暂无评论