Article Process coordination with fetch-and-increment Share on Authors: Eric Freudenthal View Profile , Allan Gottlieb View Profile Authors Info & Claims ASPLOS IV: Proceedings of the fourth international conference on Architectural support for programming languages and operating systemsApril 1991 Pages 260–268https://doi.org/10.1145/106972.106998Online:01 April 1991Publication History 27citation502DownloadsMetricsTotal Citations27Total Downloads502Last 12 Months17Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present an updated report on the NYU Ultracomputer design emphasizing recent results on programming, operating systems, caching, demand paging, and I/O.The user's view of the Ultracomputer is presented along with the hardware and software implementation.Freedom from serial bottlenecks in both hardware and software allows the Ultracomputer to obtain performance that scales nearly linearly in the size of the machine for a broad spectrum of problems.

For a wide class of problems, we obtain lower bounds for algorithms executed on certain parallel processors.These bounds show that for sufficiently large problems many known algorithms are optimal.The central result of the paper is the following sharper lower bound for permutation algorithms.Any permutation algorithm for N data items on a P processor parallel machine without shared memory requires time on the order of NlogxP/P, where K is the maximum number of processors directly connected to a single processor.In particular, a speedup on the order of P is impossible if K is bounded.

We present the design for the NYU Ultracomputer, a shared-memory MIMD parallel machine composed of thousands of autonomous processing elements. This machine uses an enhanced message switching network with the geometry of an Omega-network to approximate the ideal behavior of Schwartz's paracomputer model of computation and to implement efficiently the important fetch-and-add synchronization primitive. We outine the hardware that would be required to build a 4096 processor system using 1990's technology. We also discuss system software issues, and present analytic studies of the network performance. Finally, we include a sample of our effort to implement and simulate parallel variants of important scientific p̀rograms.

In this paper we implement several basic operating system primitives by using a "replace-add" operation, which can supersede the standard "test and set" and which appears to be a universal primitive for efficiently coordinating large numbers of independently acting sequential processors.We also present a hardware implementation of replace-add that permits multiple replace-adds to be processed nearly as efficiently as loads and stores.Moreover, the crucial special case of concurrent replace-adds updating the same variable is handled particularly well: If every processing element simultaneously addresses a replace-add at the same variable, all these requests are satisfied in the time required to process just one request.

We present the design for the NYU Ultracomputer, a shared-memory MIMD parallel machine composed of thousands of autonomous processing elements. This machine uses an enhanced message switching network with the geometry of an Omega-network to approximate the ideal behavior of Schwartz's paracomputer model of computation and to implement efficiently the important fetch-and-add synchronization primitive. We outline the hardware that would be required to build a 4096 processor system using 1990's technology. We also discuss system software issues, and present analytic studies of the network performance. Finally, we include a sample of our effort to implement and simulate parallel variants of important scientific programs.

Ellis' concurrent AVL insertion algorithm1is discussed in this correspondence. We note that obtaining a block of storage for the new AVL leaf may become a serial bottleneck for the entire insertion algorithm. We indicate a potential solution and refer the reader to another paper [1] in which the full details are given.