Parallel discrete event simulation (PDES) has been a subject of research since the late 1970s. By now we know a lot about the general outlines of the subject. However, there is still an immense amount of research and development to do. In this talk I will summarize what I believe PDES has contributed to computer science and other fields so far, what the current status is, where I think we are still deficient as a field, and where I think our R&D priorities should be in the future.

This paper describes the Altera Stratix logic and routing architecture. The primary goals of the architecture were to achieve high performance and logic density. We give an overview of the entire device, and then focus on the logic and routing architecture. The Stratix logic architecture is based on a cluster of ten 4-input LUTs and its routing consists of staggered routing lines. We describe the development of the routing architecture, including its directional bias, its direct-drive routing which reduces both area and delay. The logic array block and logic cell design is also described, and new routing structures with in the logic array block, and logic element features are described.

Artificial life embraces those human-made systems that possess some of the key properties of natural life. We are specifically interested in artificial systems that serve as models of living systems for the investigation of open questions in biology. First we review some of the artificial life models that have been constructed with biological problems in mind, and classify them by medium (hardware, software, or “wetware”) and by level of organization (molecular, cellular, organismal, or population). We then describe several “grand challenge” open problems in biology that seem especially good candidates to benefit from artificial life studies, including the origin of life and self-organi- zation, cultural evolution, origin and maintenance of sex, shifting balance in evolution, the relation between fitness and adaptedness, the structure of ecosystems, and the nature of mind.

sarily execute a simulation in the same amount of space as a sequential execution.In some cases a simulation requiring space n+k when executed sequentially might require O(nk) space when executed on n processors by CMB.

In this paper we introduce a new analytical approach to modeling the performance of systems synchronized by timestamp mechanisms, including database systems. We define the virtual time - real time (T-V) plane, and an important kind of stochastic process that we call linear Poisson processes. We show how to calculate the rate of preemption (corresponding to the rate of abortion or rollback in concurrency control mechanisms) and the waiting time until last preemption (corresponding to commit time) for linear Poisson processes. Finally, we apply this theory, analyzing one example system synchronized by the Time Warp mechanism.

A program annotated with inductive assertions is said to be verification decidable If all of the verification conditions generated from the program and assertions are formulas In a decidable theory A theory is defined, which is called Presburger array theory, containing two logical sorts integer and array of integer Addltmn, subtraction, and comparisons are permztted for integers Array access and assignment functmns are allowed Since the elements of the arrays are integers, array accesses may be nested First, it is observed that the validity of unquantlfied formulas in Presburger array theory is decidable, yet quantified formulas in general are undecldable It is then shown that, with certain restrictions, one can add a new predicate Perm(M, N)--meanlng array M is a permutation of array N--to the assertion language and still have a solvable decision problem for verification conditions generated from unquantified assertions The significance of this result is that almost all known one-array sorting programs are verlticatmn decidable when annotated with inductive assertions for proving that the output is a permutation of the input

This paper describes the capability based protection mechanisms provided by the Hydra Operating System Kernel. These mechanisms support the construction of user-defined protected subsystems, including file and directory subsystems, which do not therefore need to be supplied directly by Hydra. In addition, we discuss a number of well known protection problems, including Mutual Suspicion, Confinement and Revocation, and we present the mechanisms that Hydra supplies in order to solve them.