Grid-based computing frameworks leverage underutilized processing and storage resources. We present and evaluate a new high-performance, reliable middleware layer that can incorporate instruments into a grid. This Java based messaging system supports remote distributed control and operation of scientific instruments, such as sensors and probes, thereby significantly expanding the grid's capabilities. Various comparative measurements show that our system outperforms the top-ranked publish-sub scribe Java systems in the market. Our sofiware can reach a peak message exchange rate of 900,000 messages per second, with a latency of less than half a millisecond on a 1 GB Ethernet switch.

Machine virtualization has emerged as a key technology for server consolidation and on-demand server provisioning. To support this trend, it is essential to improve the performance of virtualization software and hence enable the efficient running of many virtual machines. We present a virtualization system that can dynamically extend the real memory of its guest virtual machines. We describe an implementation of dynamic memory extension for Linux guests running on the IBM zVM virtualization environment. Our implementation for the Linux extension is based on device drivers for accessing these dynamic memory extensions. Moreover, we show that this new capability can improve utilization and performance of the Linux guests in our virtualization environment. Specifically, memory management is improved and more virtual machines can run at a given moment. We study the utilization of dynamic memory extension of a Linux guest for a JVM heap. Running Specjbb2000 benchmark on a small virtual machine extended with dynamic memory to host the heap, we measured an improvement in transaction throughput and a 23.23% reduction in paging activity compared to an initially large machine. We further studied the implication of our experiments on the number of virtual machines that can run efficiently.

We present a new hardware-based data prefetching mechanism for enhancing instruction level parallelism and improving the performance of superscalar processors. The emphasis in our scheme is on the effective utilization of slack time and hardware resources not used for the main computation. The scheme suggests a new hardware construct, the program progress graph (PPG), as a simple extension to the branch target buffer (BTB). We use the PPG for implementing a fast pre-program counter pre-PC, that travels only through memory reference instructions (rather than scanning all the instructions sequentially). In a single clock cycle the pre-PC extracts all the predicted memory references in some future block of instructions, to obtain early data prefetching. In addition, the PPG can be used for implementing a pre-processor and for instruction prefetching. The prefetch requests are scheduled to "range" with the core requests from the data cache, by using only free time slots on the existing data cache tag ports. Employing special methods for removing prefetch requests that are already in the cache (without utilizing the cache-tag ports bandwidth) and a simple optimization on the cache LRU mechanism reduce the number of prefetch requests sent to the core-cache bus and to the memory (second level) bus. Simulation results on the SPEC92 benchmark for the base line architecture (32 K-byte data cache and 12 cycles fetch latency) show an average speedup of 1.36 (CPI ratio).

Programs in languages such as Fortran, Pascal, and C were designed and written for a sequential machine model. During the last decade, several methods to vectorize such programs and recover other forms of parallelism that apply to more advanced machine architectures have been developed (particularly for Fortran, due to its pointer-free semantics). We propose and demonstrate a more powerful translation technique for making such programs run efficiently on parallel machines which support facilities such as parallel prefix operations as well as parallel and vector capabilities. This technique, which is global in nature and involves a modification of the traditional definition of the program dependence graph (PDG), is based on the extraction of parallelizable program structures (“idioms”) from the given (sequential) program. The benefits of our technique extend beyond the above-mentioned architectures and can be viewed as a general program optimization method, applicable in many other situations. We show a few examples in which our method indeed outperforms existing analysis techniques.

We present a new framework in which considerations of both register allocation and instruction scheduling can be applied uniformly and simultaneously. In this framework an optimal coloring of a graph, called the parallel interference graph, provides an optimal register allocation and preserves the property that no false dependences are introduced, thus all the options for parallelism are kept for the scheduler to handle. For this framework we provide heuristics for trading off parallel scheduling with register spilling.

This work considers type systems that are defined by type-graphs (tgraphs), which are rooted directed graphs with order among the edges leaving each node. Tgraphs are uniquely mapped into polynomials which, in turn, are each evaluated at a special point to yield an irrational number named the tgraph's magic number . This special point is chosen using the Schanuel conjecture. It is shown that each tgraph can be uniquely represented by this magic number; namely, types are equal if and only if the corresponding magic numbers are equal. Since irrational numbers require infinite precision, the algorithm for generating magic numbers is carried out using a double-precision floating-point approximation. This approximation is viewed as a hashing scheme, mapping the infinite domain of the irrational numbers into finite computer words. The proposed hashing scheme was investigated experimentally, with the conclusion that it is a good and practical hashing method. In tests involving over a million randomly chosen tgraphs, we have not encountered a single collision. We conclude that this method for representation and management of types is practical, and offers novel possibilities for enforcing strict type matching at link time among separately compiled modules.

Programs in languages such as FORTRAN, Pascal, and which our method indeed outperforms existing analysis techniques.

This paper proposes a solution to providing a collision free channel allocation in a multihop mobile radio network. An efficient solution to this problem provides spatial reuse of the bandwidth whenever possible. A robust solution maintains the collision free property of the allocation under any combination of topological changes. The node organization algorithm presented in this paper provides a completely distributed, maximally localized execution of collision free channel allocation. It allows for parallel channel allocation in stationary and mobile networks with provable spatial reuse properties. A simpler version of the algorithm provides also a highly localized distributed coloring algorithm of dynamic graphs.

One of the overwhelming problems that software producers must contend with is the unauthorized use and distribution of their products. Copyright laws concerning software are rarely enforced, thereby causing major losses to the software companies. Technical means of protecting software from illegal duplication are required, but the available means are imperfect. We present protocols that enable software protection, without causing substantial overhead in distribution and maintenance. The protocols may be implemented by a conventional cryptosystem, such as the DES, or by a public key cryptosystem, such as the RSA. Both implementations are proved to satisfy required security criteria.

This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Boolean values or values from some bounded range, and in which approximate, rather than exact, agreement is the desired goal. Algorithms are presented to reach approximate agreement in asynchronous, as well as synchronous systems. The asynchronous agreement algorithm is an interesting contrast to a result of Fischer et al, who show that exact agreement with guaranteed termination is not attainable in an asynchronous system with as few as one faulty process. The algorithms work by successive approximation, with a provable convergence rate that depends on the ratio between the number of faulty processes and the total number of processes. Lower bounds on the convergence rate for algorithms of this form are proved, and the algorithms presented are shown to be optimal.

Current Temporal Logics are all oriented towards the description of totally ordered sequences. This limits their usefulness for reasoning about systems whose computations cannot easily be mapped into totally ordered sequences. Here, we propose a temporal logic geared towards describing partially ordered sets and apply it to dynamic distributed systems. Even though the logic we define does not have the finite model property, we establish that it has a one exponential decision procedure and a complete axiomatization.