We present a three-part software environment tailored to the areas of computer vision and image processing (CVIP). The environment is designed to provide high performance and ease of use for CVIP researchers implement...
详细信息
ISBN:
(纸本)0819408131
We present a three-part software environment tailored to the areas of computer vision and image processing (CVIP). The environment is designed to provide high performance and ease of use for CVIP researchers implementing algorithms and tasks on parallel systems. Cloner is a software reuse tool that helps a user design parallel algorithms by building on and modifying algorithms from the system library. It takes advantage of the fact that CVIP algorithms are often highly structured and that many algorithms have the same or similar structure. It is being designed as a menu-based, query-based system aimed at reducing the degree to which the user must be concerned with the details of parallelprogramming. Graph Matcher is a software tool to perform algorithm-to-architecture mapping for image processing algorithms. It consists of a library of known data-dependency structures and of mappings of these structures onto parallelarchitectures. For the regular graphs that characterize most image processing algorithms, the graph isomorphism used to identify a new algorithm graph as an instance of a library graph is performed in polynomial time. DISC (Dynamic Intelligent Scheduling and Control) is an operating system component that provides a rapid prototyping capability for execution of complex CVIP tasks on partitionable parallel systems. The scheduler addresses the problems of algorithms with execution times that depend on the image data and processing scenarios that vary dynamically based on the input image.
parallelization of univariate p-adic lifting, a procedure important in modern gcd and factorization algorithms, is presented. The strategy is to take the fastest known sequential algorithm and parallelize its key step...
详细信息
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.< >
This paper presents near constant time associative parallel lexing (APL) algorithms. The best time complexity thus far claimed on parallel lexing is (log n) (n denotes the number of input characters) for the parallel ...
详细信息
ISBN:
(纸本)0818626720
This paper presents near constant time associative parallel lexing (APL) algorithms. The best time complexity thus far claimed on parallel lexing is (log n) (n denotes the number of input characters) for the parallel prefix lexing (PPL) algorithm. The linear state recording step in the PPL algorithm, which needs to be done only once for each grammar, has been ignored in claiming the log n time complexity for the PPL algorithm. Furthermore, the PPL algorithm does not consider recording line numbers for the tokens and distinguishing identifier tokens as keyword or user-identifier. The APL algorithms perform all of these functions. Thus, without considering the efforts spent on these functions, the APL algorithm takes constant time since every step depends on the length of the tokens, not on the length of the input. Generalizing and including these extra functions, the APL algorithm takes near constant time.
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.
暂无评论