Clarifications and Corrections To 'Performance Analysis of a Generalized Class of m-Level Hierarchical Multiprocessor Systems' (Mar 1992 129-138)
Several items in the above-titled work areclarified and corrected.
Algorithms and Bounds for Shortest Paths and Diameter in Faulty Hypercubes
In an n-dimensional hypercube Qn, with the fault set mod F mod >2/sub n-2/, assuming Sand D are not isolated, it is shown that there exists a path of length equal to at mosttheir Hamming distance plus 4. An algorithm with complexity O( mod F mod logn) ...
Cost and Time-Cost Effectiveness of Multiprocessing
Speedup and efficiency, two measures for performance of pipelined computers, are nowused to evaluate performance of parallel algorithms for multiprocessor systems. However, these measures consider only the computation time and number of processors used ...
Generalized Measures of Fault Tolerance in n-Cube Networks
It is shown that for a given p (math), the n-cube network can tolerate up to p2/sup(n-p)/-1 processor failures and remains connected provided that at most p neighbors of any nonfaulty processor are allowed to fail. This generalizes the result for p=n-1,...
On the Granularity and Clustering of Directed Acyclic Task Graphs
The authors consider the impact of the granularity on scheduling task graphs. Schedulingconsists of two parts, the processors assignment of tasks, also called clustering, and theordering of tasks for execution in each processor. The authors introduce ...
Dynamic Synchrony Among Atomic Actions
Synchrony continues to be an important concern in concurrent programming. Existinglanguages and models have introduced a great diversity of constructs for expressing and managing synchronization among sequential processes or atomic actions. The authors ...
Performance Evaluation of the Time-Stamp Ordering Algorithm in a Distributed Database
Time-stamp ordering is one of the consistency preserving algorithms that is used indistributed databases. F. Baccelli (1987) has introduced a queueing model thatincorporates the fork-join and resequencing synchronization constraints to analyze ...
An Implementation of F-Channels
An F-channel can permit as much concurrency as a non-first-in-first-out (FIFO)communication channel and yet retain the properties of a FIFO channel that lead tosimplicity of reasoning in design and proofs of the correctness of distributed algorithms.The ...
A Network Flow Model for Load Balancing in Circuit-Switched Multicomputers
In multicomputers that utilize circuit switching or wormhole routing, communicationoverhead depends largely on link contention-the variation due to distance between nodesis negligible. This has a major impact on the load balancing problem. In this case ...
Prediction-Based Dynamic Load-Sharing Heuristics
Presents dynamic load-sharing heuristics that use predicted resource requirements ofprocesses to manage workloads in a distributed system. A previously developed statisticalpattern-recognition method is employed for resource prediction. ...
Declustering: A New Multiprocessor Scheduling Technique
The authors present a new compile-time scheduling heuristic called declustering, whichschedules acyclic precedence graphs that fit the synchronous data flow (SDF) modelonto multiprocessor architectures. This technique accounts for ...
A Unified Formalization of Four Shared-Memory Models
The authors present a data-race-free-1, shared-memory model that unifies four earliermodels: weak ordering, release consistency (with sequentially consistent specialoperations), the VAX memory model, and data-race-free-0. Data-race-free-1 unifies ...
A Sliding Memory Plane Array Processor
A mesh-connected single-input multiple-data (SIMD) architecture called a sliding memory plane (SliM) array processor is proposed. Differing from existing mesh-connected SIMD architectures, SliM has several salient features such as a sliding memory plane ...