This paper describes a new and different paradigm for real-time command and control that we show can provide a static, polynomial-time scheduling algorithm. Current efforts in real-time scheduling have been unable to predict system performance, and use a unpredictable "dynamic" scheduling algorithm. The Nation's Air Traffic Control (ATC) System has been unable to satisfy performance requirements, and is extremely expensive. An editorial in "USA Today" (419 -1999) cites expenditures in ATC at $41 billion. But, current multiprocessor technology cannot do the job.

This paper describes an initial design of an associative processor for implementation using field-programmable logic devices (FPLDs). The processor is based loosely on earlier work on the STARAN computer, but updated to reflect modern design practices. We also draw on a large body of research at Kent State on the ASC and MASC models of associative processing, and take advantage of an existing compiler for the ASC model. The resulting design consists of an associative array of 8-bit RISC Processing Elements (PEs), operating in byte-serial fashion under the control of an Instruction Stream (IS) Control Unit that can execute assembly language code produced by a machine-specific back-end compiler.

When one is concerned with maximizing overall program throughput, task mapping in a heterogeneous computing environment presents the problem of which computing unit(s) is best suited to perform each task. This paper explores the concept that finding a "better" starting point for the static mapping process will provide a better opportunity for success. A starting point based on a computation task graph centroid, similar to that of masses in the gravity system, is derived such that the centroid of the task graph is the mapping starting point. Comparisons based on experimentation are then made using the HP Greedy mapping technique (Leangsuksun and Potter, 1994) while varying the starting point from beginning, centroid and end of the problem. Results show that the task centroid mapping technique does not increase the complexity of the mapping process but does result in an improved overall program throughput.>

Abstract The searching power of massively parallel associative computers is an under used and under investigated capability that can be used to facilitate software development. This paper describes the development of a context sensitive compiler for pattern‐matching languages using that searching power. The described compiler was implemented on the STARAN parallel computer and the compiled OPS5 programs were also executed on the STARAN obtaining an estimated throughput of 6000 rules per second. The described compilation of production rules into equivalent procedural rules is completely data parallel, with the degree of parallelism depending on the number of tokens in the program being compiled. During any one step of the context‐sensitive analysis, the entire program is processed in constant time.

An associative data-parallel compilation model of logic programs capable of answering queries with unspecified relations concerning the given objects is described. The model benefits from the synergy resulting from associative search, data-parallelism during goal reduction, and the use of low-level code to invoke the subgoals and savings in data-transfers resulting from the presence of global registers. The use of associative tables extends the power of logic programming to answer a large class of queries and derive unspecified relation-names for the given objects. In contrast to the interpretation based on a pure data parallel model, this model does not suffer from data sequentiality caused by the presence of multiple-occurrence variables in the goals. The model also handles variable aliasing in the clauses efficiently using the associative data-parallel search and data-parallel assignment property.>

The authors describe the range of hardware variations of array processors, a form of SIMD (simple instruction stream, multiple dates stream architecture), comparing and contrasting the significant differences among them and briefly illustrating the wide range of algorithms that can effectively utilize them. Three applications are reviewed. The first application, image convolution, represents the traditional numerically computationally intensive areas of application. SIMD array processors are sufficiently powerful to process digital imagery in real time easily. The second application, an example of real-time database management, is the air traffic control problem. The problem cannot be solved today by networks of computers that are successfully used in similar, less time-critical applications. With an array processor there is sufficient real time remaining after the present system tasks are accomplished to realize additional system enhancements. The third application area, graph algorithms, which is more theoretical, is representative of problems for which the simplicity of the array processor solution results in an execution time better than the best theoretical case for a conventional sequential implementation.>

Although motion is one of the most fundamental aspects of the visual world, its use has not been widely explored in the field of scene description. This correspondence describes a program that demonstrates the feasibility of segmenting a scene into regions on the basis of velocity. A velocity measure is obtained by determining the amount of displacement of a reference feature between two pictures of the same scene. The pictures are taken only a short time apart so that the reference features can be correlated between the pictures on the basis of spatial position alone. This velocity measurement is associated with absolute reference points superimposed over the scene. It is assumed that all parts of an object have the same velocity measurement. Thus the velocity measurements associated with the reference points provide a means of classifying them as ``belonging'' to the same object. Points ``inside'' moving objects fall into either of two velocity measurement classes, which are easily correlated. Since the velocity of an object is independent of its color, a scene is segmented into regions that contain complete objects even if the objects are not monochromatic.