Abstract
It is known that in multiprocessing systems composed of many identical processing units operating in parallel, certain timing anomalies may occur; e.g., an increase in the number of processing units can cause an increase in the total length of time needed to process a fixed set of tasks. In this paper, precise bounds are derived for several anomalies of this type.
Keywords
MultiprocessingSet (abstract data type)Parallel computingComputer scienceProcess (computing)Operating systemProgramming language
Related Publications
Production and Stabilization of Real-Time Task Schedules
A model for multiprocessor control is considered in which jobs are broken into various pieces, called tasks . Tasks are executed by single processing units. In this paper the st...
<i>Aquarium</i>: an automatic data-processing and experiment information management system for biological macromolecular crystallography beamlines
With the popularity of hybrid pixel array detectors, hundreds of diffraction data sets are collected at a biological macromolecular crystallography (MX) beamline every day. Ther...
Memory devices and applications for in-memory computing
Traditional von Neumann computing systems involve separate processing and memory units. However, data movement is costly in terms of time and energy and this problem is aggravat...
PEAR: a fast and accurate Illumina Paired-End reAd mergeR
Abstract Motivation: The Illumina paired-end sequencing technology can generate reads from both ends of target DNA fragments, which can subsequently be merged to increase the ov...
Concurrent programming of intelligent robots
Real time intelligent robots usually consist of more than one processing unit (pu) to ensure parallel operation of several functions. Each pu in a robot executes repetitive moni...
Publication Info
- Year
- 1966
- Type
- article
- Volume
- 45
- Issue
- 9
- Pages
- 1563-1581
- Citations
- 1613
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1613
OpenAlex
Cite This
Ronald Graham
(1966).
Bounds for Certain Multiprocessing Anomalies.
Bell System Technical Journal
, 45
(9)
, 1563-1581.
https://doi.org/10.1002/j.1538-7305.1966.tb01709.x
Identifiers
- DOI
- 10.1002/j.1538-7305.1966.tb01709.x