A parallel implementation of selection sorting algorithms is presented that uses a ring-connected array of processors, in which each processor has the same amount of memory. The scheme allows all processors to have the same amount of memory with a small fragmentation loss. Uniformity in the size of the memories provides advantages from the viewpoint of manufacture, maintenance, inventory, item placement, and many other aspects of system design. These memories can, together, function as an interleaved memory for a general-purpose computer. Hence, it is possible to build a medium-scale system in which parallel-sort is implemented as a primitive, like block-move, without a large increment in hardware complexity and cost. An analysis is presented that shows how to improve performance by overlapping comparisons with memory accesses and how to achieve performance improvement by applying carry-look-ahead techniques to comparison.>

One of the most important considerations for a dataflow multiprocessor is the algorithm by which the nodes of a program graph are allocated for execution to its processors. In the case of the static type of architecture one must consider pipelining as well as spatial concurrency. This paper uses a graph partitioning scheme to aid in the design of such algorithms and selection of the associated interconnection topology. The scheme first refines the usual dataflow program graph and then partitions it into “trees.” Our study shows that the hypercube interconnection accommodates these trees in a way that allows as to develop an algorithm that places producer nodes (of a dataflow graph) nears their consumers to keep the message path very short. The algorithm achieves concurrency in simultaneous execution of subgraphs that involve parallel operations, e.g., array operations, and subgraphs that are highly iterative or recursive. An analytical model is given to evaluate the performance of the algorithm.

A society model, which characterizes the behavior and procedure of offices, is proposed. It is our belief that an office system capable of dealing with all real office problems only through the modeling of the internal behavior of an office can be developed. In this society model, office entities are viewed as agents . An agent is modeled as a microsociety of interacting knowledge sources. Within the microsociety, there exists a microknowledge exchange system , which provides a set of microknowledge exchange protocols as a coordination system among those knowledge sources during their cooperative reasoning process. An office is then modeled as a society of various interacting agents using their knowledge to complete the office goals cooperatively. It is this unified view that allows offices to be modeled in a flexible and general way.

Algorithms are described and analyzed for the efficient evaluation of the primitive operators of a relational algebra on a database machine architecture. The architecture contains a RAM divided up into partitions, each partition having a separate server. Tuples from the first operand relation are stored in linked lists in the partitioned RAM via bit and pointer arrays based on hashed column values. Each tuple in the second operand relation is either deposited in the corresponding partition server queue based on the hashed value, or it is ignored. Cross-referencing involved in the operations is removed without performing a sorting operation, which significantly reduces the time complexity. A procedure is also presented for computing the optimal number of partition servers for different applications.

A pipeline and parallel architecture is described and analyzed for efficient support of database management systems. The main feature of the architecture is a RAM consisting of two bit-arrays, one word-array, and one memory bank. Through the use of the RAM, cross referencing involved in the join and project operations can be removed, without the need for sorting. Further performance improvements are achieved by using parallelism in tuple cancatenation and tuple comparison via a set of servers. The architecuture is quite suitable for a wide range of database applications, especially those requiring a high percentage of cross referencing. A hardware simulator was developed for determining the optimal number of servers for different applications.

Protection of data in a database against unauthorized disclosure, alteration, or destruction is an important aspect of a multiuser database system. In a system which uses a celiular-logic device as a means for data management applications, protection can be achieved in part by associating security windows with queries. This paper describes a mechanism for dynamically creating these windows for cellular-logic devices. The mechanism mainly benefits from the associative techniques such as content and context searches, tagging and marking data, etc. These techniques allow the windows to be created physically by simultaneously activating related access control decision procedures, which implement access control decisions employed by the system, to mask out those data to which the user does not have the right of access. Furthermore, they enable the content-dependent security decisions to be efficiently implemented, eliminating the drawbacks found in conventional systems. Thus, a query accessing to a protected database system is identical to a query accessing to its companion window. An implementation of this mechanism on the cellular-logic device CASSM is also presented.