𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines

✍ Scribed by Eunice E. Santos

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
360 KB
Volume
62
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

The problem of designing efficient parallel algorithms for summing and prefix summing for certain classes of the LogP model is studied. We present optimal algorithms for summing and show that any optimal summing algorithm must have a certain inherent structure. Moreover, we present optimal or near-optimal algorithms for prefix summing for both non-commutative and commutative binary operators. Furthermore, we show that the optimal algorithms for prefix summing for these two types of operators are not equivalent.

πŸ“œ SIMILAR VOLUMES

Exact algorithms for scheduling multiple
Exact algorithms for scheduling multiple families of jobs on parallel machines
✍ Zhi-Long Chen; Warren B. Powell πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 140 KB

## Abstract In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent o

Approximation algorithms for minimizing
Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel
✍ Joseph Y-T. Leung; Haibing Li; Michael Pinedo πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 214 KB

## Abstract We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is re

Efficient Parallel Algorithms for Optima
Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network
✍ Biing-Feng Wang πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 128 KB

In this paper, we propose efficient parallel algorithms on the EREW PRAM for optimally locating in a tree network a path-shaped facility and a tree-shaped facility of a specified length. Edges in the tree network have arbitrary positive lengths. Two optimization criteria are considered: minimum ecce

FINITE ELEMENT ALGORITHMS FOR DYNAMIC SI
FINITE ELEMENT ALGORITHMS FOR DYNAMIC SIMULATIONS OF VISCOELASTIC COMPOSITE SHELL STRUCTURES USING CONJUGATED GRADIENT METHOD ON COARSE GRAINED AND MASSIVELY PARALLEL MACHINES
✍ SUNG YI; M. FOUAD AHMAD; HARRY H. HILTON πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 237 KB πŸ‘ 2 views

Recently much attention has been paid to high-performance computing and the development of parallel computational strategies and numerical algorithms for large-scale problems. In this present study, a ΓΏnite element procedure for the dynamic analyses of anisotropic viscoelastic composite shell struct