Collected works of Kenneth E. Batcher, emeritus professor, and works inspired by his research and scholarship.
Browse the Kenneth E. Batcher Collection: Papers from the Parallel and Associative Computing Laboratory Collections
Simulation of Enhanced Meshes with MASC, a MSIMD ModelMASC (for Multiple Associative Computing) is a joint control parallel, data parallel model that provides a practical, highly scalable model that naturally supports small to massive parallelism and a wide range of applications. In this paper, we present efficient algorithms for a MASC model with a 2-D mesh to simulate enhanced meshes. Let MASC(n, j) denote a MASC model with n processing elements and j instruction streams. It is shown that a MASC(n, j) model with a 2-D mesh is strictly more powerful than a √n × √n MMB (Mesh with Multiple Broadcasting) when j =Ω(√n ). Simulation of a √n × √n MMB by MASC(n, j) with a 2-D mesh runs in O(1) time and requires no extra memory. Simulating a √n × √n BRM (Basic Reconfigurable Mesh) with MASC(n, j) with a 2-D mesh takes O(√n) extra time with O(n) extra memory when j =Ω(√n ). The reverse simulations of MMB or BRM with MASC with a 2-D mesh is also given. These simulations not only provide information about the power of the MASC model and also provide an automatic conversion of numerous algorithms designed for enhanced meshes to the MASC model. |
Solving a 2D knapsack problem on an associative computer augmented with a linear network1996This paper describes a parallelization of the sequential dynamic programming method for solving a 2D knapsack problem where multiples of n rectangular objects are optimally packed into a knapsack of size L × W and are only obtainable with guillotine-type (side to side) cuts. The parallel algorithm is described and analyzed for the associative model. The associative model (ASC) for parallel computation supports a generalized version of an associative style of computing that has been used since the introduction of associative SIMD computers in the early 1970's. In particular, this model supports data parallelism, constant time maximum and minimum operations, one or more instruction streams (ISs) which are sent to an equal number of partition sets of processors, and assignment of tasks to the ISs using control parallelism. This algorithm runs in O(W(n+L+W)) time using O(L) processors, where L ≥ W for a 2D knapsack problem with a capacity of L × W. This result is cost optimal with respect to the best sequential implementation. Moreover, an efficient ASC algorithm for this well-known problem should give insight to how the associative model compares to other parallel models. |
Solving a 2D Knapsack Problem Using a Hybrid Data-Parallel/Control Style of Computing2004This paper describes a parallel solution of the sequential dynamic programming method for solving a NP class, 2D knapsack (or cutting-stock) problem which is the optimal packing of multiples of n rectangular objects into a knapsack of size LW×and are only obtainable with guillotine-type (side to side) cuts. Here, we describe and analyze this problem for the associative model. Since the introduction of associative SIMD computers over a quarter of a century ago, associative computing and the data-parallel paradigm remain popular. The MASC (Multiple instruction stream ASsociative Computer) parallel model supports a generalized version of an associative style of computing. This model supports data parallelism, constant time maximum and minimum operations, one or more instruction streams (ISs) which are sent to an equal number of partition sets of processors, and assignment of tasks to ISs using control parallelism. We solve this NP class problem with a parallel algorithm that runs in O(W(n+L+W)) time using L processors, where L≥W for a 2D knapsack problem with a capacity of L×W. The new multiple IS version using LW processors and max{L,M} ISs runs in O(n+L+W) given practical hardware considerations. Both of these results are cost optimal with respect to the best sequential implementation. Moreover, an efficient MASC algorithm for this well-known problem should give insight to how the associative model compares to other parallel models such as PRAM. |
Sorting Networks and Their Applications1968To achieve high throughput rates today's computers perform several operations simultaneously. Not only are I/O operations performed concurrently with computing, but also, in multiprocessors, several computing operations are done concurrently. A major problem in the design of such a computing system is the connecting together of the various parts of the system (the I/O devices, memories, processing units, etc.) in such a way that all the required data transfers can be accommodated. One common scheme is a high-speed bus which is time-shared by the various parts; speed of available hardware limits this scheme. Another scheme is a cross-bar switch or matrix; limiting factors here are the amount of hardware (an m × n matrix requires m × n cross-points) and the fan-in and fan-out of the hardware. |
STARAN parallel processor system hardware05/06/1974The parallel processing capability of STARAN resides in n array modules (n≤32). Each array module contains 256 small processing elements (PE's). They communicate with a multi-dimensional access (MDA) memory through a "flip" network, which can permute a set of operands to allow inter-PE communication. This gives the programmer a great deal of freedom in using the processing capability of the PE's. At one stage of a program, he may apply this capability to many bits of one or a few items of data; at another stage, he may apply it to one or a few bits of many items of data. |
STARAN Series E1977STARAN Series E is an enhanced version of the STARAN parallel array processor. Multi-dimensional-access data storage and high speed control storage have been increased several-fold. Faster IC's and new processing algorithms improve the processing rates significantly. A new I/O unit allows faster and more flexible input and output of data. The cost impact of these changes has been minimized by using standard parts which were not available when the first STARAN was built. In this paper we discuss the enhancements and the reasons they were incorporated. |
STARAN: An Associative Approach to Multiprocessor Architecture06/20/1975Goodyear technical paper AP-122279 Rev. 1 (From front matter) STARAN is a multiprocessor of unique capabilities which can be utilized to provide higher throughput for lower cost in data processing systems where a high degree of parallelism exists. This paper describes the STARAN architecture and software and the resulting system capabilities. Several application examples are also discussed. |
STARAN/RADCAP Hardware Architecture1973Hardware architecture is described for RADCAP, the operational associative array processor (AP) facility installed at Rome Air Development Center (RADC), N.Y. Basically, this facility consists of Goodyear Aerospace STARAN parallel processor and various peripheral devices interfaced with a Honeywell Information Systems (HIS) 645 sequential computer, which runs under the Multics time-shared operating system. The hardware of STARAN/RADCAP is described with particular emphasis on the parallel processing elements. |
Study of multistage SIMD interconnection networks04/1978Four SIMD multistage networks—Feng's data manipulator, STARAN flip network, omega network, and indirect binary n-cube—are analyzed. Three parameters—topology, interchange box, and control structure—are defined. It is shown that the latter three networks use equivalent topologies and differences in their capabilities result from the other parameters. An augmented data manipulator network using a modified control structure to perform more single pass interconnections than the other networks is presented. Some problems may be solved more efficiently if the 2n processing elements of an SIMD machine can be partitioned into submachines of size 2r. Single and multiple control partitioning are defined. The capabilities of these multistage networks to perform in these partioned environments are discussed. |