Summary form only given, as follows. Genetic algorithms are randomized (but not directionless) search procedures that maneuver through complex spaces looking for optimal solutions. They are based on the mechanics of n...
详细信息
Summary form only given, as follows. Genetic algorithms are randomized (but not directionless) search procedures that maneuver through complex spaces looking for optimal solutions. They are based on the mechanics of natural selection and natural genetics. These procedures, which are implicitly parallel in structure, make few assumptions about the problem domain and can thus be applied to a broad range of problems. A succession of generations created by reproduction, crossover, and mutation constitutes a parallel search through the search space, favoring regions with above average fitness. The crossover operation is of vital importance, since a loss of diversity in a generation will generally yield premature convergence, pushing the search toward a suboptimal solution. The author presents informatic crossover, which is based on Shannon's information theory. It uses conditional entropy for selecting the crossing site in crossover and has been shown to promote diversity in generations.
parallel processing of relational queries has received considerable attention of late. However, in the presence of data skew, the speedup from conventional parallel join algorithms can be very limited, due to load imb...
详细信息
ISBN:
(纸本)0818620528
parallel processing of relational queries has received considerable attention of late. However, in the presence of data skew, the speedup from conventional parallel join algorithms can be very limited, due to load imbalances among the various processors. Even a single large skew element can cause a processor to become overloaded. In this paper, we propose a parallel sort merge join algorithm which uses a divide-and-conquer approach to address the data skew problem. The proposed algorithm adds an extra scheduling phase to the usual sort, transfer and join phases. During the scheduling phase, a parallelizable optimization algorithm, using the output of the sort phase, attempts to balance the load across the multiple processors in the subsequent join phase. The algorithm naturally identifies the largest skew elements, and assigns each of them to an optimal number of processors. Assuming a Zipf-like distribution for data skew, the algorithm is demonstrated to achieve very good load balancing for the join phase in a CPU-bound environment, and is shown to be very robust relative to the degree of data skew and the total number of processors.
It is known that many problems which can be solved sequentially by dynamic programming, are in the class TVC. Indeed most of these problems takes 0(log2 n) time on parallel models like CREW PRAM, but the number of pro...
详细信息
For programmable high-speed digital signal processing devices the proper architecture has to be carefully selected according to the algorithms to be implemented. The appropriate number of arithmetic units depends on t...
详细信息
For programmable high-speed digital signal processing devices the proper architecture has to be carefully selected according to the algorithms to be implemented. The appropriate number of arithmetic units depends on the degree of parallelism of the signal processing algorithm. The question of parallelism of algorithms is discussed. For the efficient exploitation of a given signal processor hardware, an appropriate processor schedule is necessary. In two examples different approaches for multiprocessor architectures are discussed.< >
Some general conditions under which the specification of a concurrent system can be expressed as the conjunction of specifications for its component processes are explored. A lattice-theoretic fixed-point theorem abou...
详细信息
Some general conditions under which the specification of a concurrent system can be expressed as the conjunction of specifications for its component processes are explored. A lattice-theoretic fixed-point theorem about increasing functions is proved, and examples of its application in several areas of computing science are given. Some consequences are drawn for the design of concurrent algorithms, high-level programming languages, and fine-grained concurrent computer architectures.< >
Mesh of pyramids and pyramid of meshes implementations of an iterative image-restoration algorithm are proposed. These implementations are based on a single-step regularized iterative restoration algorithm. Both archi...
详细信息
Mesh of pyramids and pyramid of meshes implementations of an iterative image-restoration algorithm are proposed. These implementations are based on a single-step regularized iterative restoration algorithm. Both architectures are described as a composition of a mesh and a pyramid. They are compared in terms of area of the VLSI chip and its computation time.< >
An approach for integrating task and parallel architecture characteristics is presented, with the objectives of easing the burden of parallelprogramming on the user and of increasing the system efficiency through mor...
详细信息
An approach for integrating task and parallel architecture characteristics is presented, with the objectives of easing the burden of parallelprogramming on the user and of increasing the system efficiency through more informed embedding, partitioning, and scheduling. The proposed approach uses the concepts of parallel primitives and a primitives table that serves as the knowledge base for the system. parallel primitives are parallel SIMD computations and can be used to write parallel programs. The primitives table stores the specifications of each primitive. In addition, for each primitive several alternative implementations corresponding to alternative network structures are provided and stored in the table. A layered implementation of a parallel processing system with parallel primitives is presented. The authors also examine the positive implications of the primitives table on scheduling, as well as on determining the optimal machine configurations for tasks using precedence graphs. The latter problem is shown to be NP-complete. However, a linear algorithm is found for the case in which the precedence graph is a tree.< >
The array constructs of Fortran 90 (formerly called Fortran 8*) map naturally onto SIMD (single-instruction-stream, multiple-data-stream) architectures that support a data parallelprogramming style, such as that of t...
详细信息
The array constructs of Fortran 90 (formerly called Fortran 8*) map naturally onto SIMD (single-instruction-stream, multiple-data-stream) architectures that support a data parallelprogramming style, such as that of the Connection Machine computer system. The FORALL statement, an extension to Fortran 90 allowing for the expression of simultaneous execution of certain DO loop bodies, enhances this natural fit. A Fortran 90 compiler for data parallel machines is extended naturally to handle the FORALL statement. The data structures and algorithms used to effect this extension are described, and some examples of source code fragments and the target operations generated for them are presented.< >
The Viterbi algorithm (VA) is a common application of dynamic programming. Since it contains a nonlinear ACS (add-compare-select) feedback loop, this loop is the bottleneck in high-data-rate implementations. It is sho...
详细信息
The Viterbi algorithm (VA) is a common application of dynamic programming. Since it contains a nonlinear ACS (add-compare-select) feedback loop, this loop is the bottleneck in high-data-rate implementations. It is shown that, asymptotically, the ACS feedback no longer has to be processed recursively, i.e. there is no feedback, resulting in negligible performance loss. This can be exploited to derive purely feedforward architectures for Viterbi decoding, so that a modular cascadable implementation results. By designing one cascadable module, any speedup can be achieved simply by adding modules to the implementation. It is shown that optimization criteria, e.g. minimum latency or maximum hardware efficiency, are met by very different architectures.< >
暂无评论