Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Physical Sciences and Mathematics
Parallel Divide And Conquer, Per Brinch Hansen
Parallel Divide And Conquer, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
We develop a generic divide and conquer algorithm for a parallel tree machine. From the generic algorithm we derive balanced, parallel versions of quicksort and the fast Fourier transform by substitution of data types, variables and statements. The performance of these algorithms is analyzed and measured on a Computing Surface configured as a tree machine with distributed memory.
Do Hypercubes Sort Faster Than Tree Machines?, Per Brinch Hansen
Do Hypercubes Sort Faster Than Tree Machines?, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
We develop a balanced, parallel quicksort algorithm for a hypercube and compare it with a similar algorithm for a binary tree machine. The performance of the hypercube algorithm is measured on a Computing Surface.
A Generic Multiplication Pipeline, Per Brinch Hansen
A Generic Multiplication Pipeline, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This paper illustrates the benefits of developing generic algorithms for parallel programming paradigms which can be adapted to different applications. We consider a combinatorial problem called tuple multiplication. This paradigm includes matrix multiplication and the all-pairs shortest paths problem as special cases. We develop a generic pipeline for tuple multiplication. From the generic algorithm we derive pipelines for matrix multiplication and shortest paths computation by making substitutions of data types and functions. The performance of the matrix multiplication pipeline is analyzed and measured on a Computing Surface.
A Simulation Of Demand-Driven Dataflow: Translation From Lucid Into Mdc Language, George K. Thiruvathukal, Thomas W. Christopher
A Simulation Of Demand-Driven Dataflow: Translation From Lucid Into Mdc Language, George K. Thiruvathukal, Thomas W. Christopher
Computer Science: Faculty Publications and Other Works
Message Driven Computation (MDC) is a model of computation with which they have been experimenting at the Illinois Institute of Technology. The authors aim to prove the viability of MDC in practice for the expression of parallel algorithms and the implementation of functional and dataflow programming languages. In the paper they discuss their implementation of the Lucid programming language in MDC. The discussion presents a subset of Lucid which illustrates the principles of Lucid, Message Driven Computing, and the translation into and the interpretation of dataflow graphs.