High-performance computing (HPC) systems consume a significant amount of power, resulting in high operational costs, reduced reliability, and wasting of natural resources. Therefore, power consumption has become an increasingly important design constraint in high-performance clusters. In this regard, research on power-aware HPC has emerged. While most research has focused at understanding and utilizing applicationspsila behavior to scale down the CPU for energy savings, this paper demonstrates the positive impact of modern interconnects in delivering energy-efficiency in high-performance clusters. In this work, we first present the power-performance profiles of the Myrinet-2000 and Quadrics QsNetIIat the user-level and MPI-level in comparison to a traditional, non-offloaded Gigabit Ethernet. Such information enables us to devise a power-aware MPI runtime library that automatically and transparently performs message segmentation and re-assembly in order to increase energy savings. Secondly, by designing and evaluating a number of all-gather collectives, we argue that it is possible to increase the energy-efficiency of a cluster by optimizing its messaging layers.

Approximate analytical queuing network models for expected message packet delay in 2-level and 3-level hierarchical ring interconnection networks (INs) are developed. A major class of traffic carried by these INs consists of cache line transfers between processor caches and remote memory modules in shared-memory multiprocessors. Such traffic consists of short, fixed-length messages; they can be conveniently transported by the slotted-ring transmission technique which is studied. The packet delay results derived from the models are shown to be quite accurate when checked against a simulation study. As well as facilitating analysis, the analytical models can be used to determine optimal sizes for the rings at different levels in the hierarchy, where optimality is in terms of minimizing average packet delay.

Analytical queueing network models for expected message delay in 2-level and 3-level hierarchical-ring interconnection networks (INs) are developed. Such networks have recently been used in commercial and research prototype multiprocessors. A major class of traffic carried by these INs consists of cache line transfers, and associated coherency control messages, between processor caches and remote memory modules in shared-memory multiprocessors. Memory modules are assumed to be evenly distributed over the processor nodes. Such traffic consists of short, fixed-length messages. They can be conveniently transported using the slotted ring transmission technique, which is studied here. The message delay results derived from the models are shown to be quite accurate when checked against a simulation study. The comparisons to simulations include heavy traffic situations where queueing delays in ring crossover switches are significant for ring utilization levels of 80 to 90%. As well as facilitating analysis, the analytical models can be used to determine optimal sizes for the rings at different levels in the hierarchy under specified traffic distributions in a system with a given total number of processor nodes. Optimality is in terms of minimizing average message delay. A specific example of such a design exercise is provided for the uniform traffic case.

Upper bounds on message delay and throughput are developed for two networks that have been used in recent multiprocessor systems. Two-dimensional mesh networks with bidirectional links and no end-around connections are compared to bus-type hierarchical networks that use segmented rings for the interconnection paths at each level of the hierarchy. Wormhole routing of short, fixed-length messages is used in the mesh networks, while a complete message can be switched between ring segments in one switch time in the hierarchical networks. It is found that three-level hierarchical systems perform somewhat better than mesh systems with respect to the basic bounds criteria that are developed.

The authors respond to section III of the above-titled work (ibid., vol.42, no.6, pp.735-737, June 1993), in which it is shown that their medium access control (MAC) protocol for rings (bid., vol.39, no.3, pp.289-299, Mar. 1990) cannot be implemented with minimum delay. They point out some differences in terminology and provide further clarification of their work.>

A novel, hybrid protocol LAN called TORNET2 is proposed, and its performance is evaluated. TORNET2 is a ring intended for high-speed applications in the 100 Mb/s range. Short-packet, high-priority traffic is handled by the register insertion technique. Combining this protocol with the early-release token protocol for handling low-priority asynchronous traffic is the novel aspect of TORNET2. The hybrid protocol operates in such a way that high-priority packets may be embedded in low-priority packets. This results in the best possible transfer delay for the high-priority traffic. In fact, the high-priority traffic is unaffected by the presence of low-priority traffic. Low-priority traffic is not locked out by high-priority traffic, but its transfer delay performance degrades as the volume of high-priority traffic increases. An approximate performance analysis of the TORNET2 network along with simulation results to verify the analysis is presented.>

A set of language-independent schedulability analysis techniques is presented. Utilizing knowledge of implementation- and hardware-dependent information in a table-driven fashion, these techniques provide accurate worst-case time bounds and other schedulability information. A prototype schedulability analyzer has been developed to demonstrate the effectiveness of these techniques. The analyzer consists of a partially language-dependent front-end, targeted at real-time Euclid, a real-time language specifically designed with a set of schedulability analysis provisions built-in, and a language-dependent back-end. The analyzer has been used on a number of realistic real-time programs run on a multiple-microprocessor system. Predicted program performance differs only marginally from the actual performance.>

A slotted-ring protocol that performs well across the full range of message length distributions is presented. The relative performance of the protocol is best at low to medium ring utilization, which is the most usual operating condition for local area computer networks. The protocol is not subject to the normal requirement for repeating source and destination addresses in each slot of a multiple-slot message. This reduced overhead feature is a main reason for the performance gains that are achieved. The protocol does not depend on any central control station for assigning slot usage to individual stations. However, it does require each ring station to keep track of the current status and source station usage of each slot on the ring. Implementation of the protocol would require significantly more complex logic circuits than are normally needed in either token rings or conventional slotted rings, and error recovery would be more difficult. Hence, its main value is that it serves as an indicator of the maximum achievable performance of the slotted format for local computer network rings operating at low to medium utilization levels under fully distributed access control.>

An analytic approximation for the blocking probability of a circuit-switched, multipath multistage interconnection network when it is required to perform arbitrary permutations under local control is presented. An analytic approximation for the expected number of conflict-free permutations realizable by a network in one pass under local control is also presented. In addition, an analytic approximation for the expected number of passes through a network required to realize an arbitrary permutation under local control is presented. These models give a quantitative measure of a network's ability to perform arbitrary permutations and of the inherent blocking in a network. These models are used to analyze two variations of banyan networks that have been discussed in the literature: dilated and augmented banyan networks. It is shown that these networks can be designed with very low blocking probabilities under permutation request patterns, and that they can be designed to realize almost all permutations in one pass under local control.

A scheme for using cache-based hardware to provide simple and efficient message-passing support for message-based software systems on a tightly-coupled, shared-bus multiprocessor is described. This approach is based on the utilization of the existing interprocessor communications medium, the shared bus, to effect the exchange of single-word messages. Communication between processes is accomplished over logical channels using simple, blocking send and receive primitives. The physical processor/channel interface is designed so that the message transfer primitives can be implemented as single machine instructions, namely store and fetch. Special-purpose caches, called message caches, mediate channel operations and effect the exchange of messages over the shared bus.>

We present analytic models for the blocking probability of both unique path and multiple path multistage interconnection networks under the assumption of either permutation or random memory request patterns. The blocking probability of an interconnection network under the assumption of permutation requests is a quantitative measure of the network's permutation capability. We compare the performance of networks with approximately equivalent hardware complexity. It is shown that variations of banyan networks can be designed with extremely low blocking probabilities under the assumption of permutation requests.

An execution model that supports program reantrancy, recurslon, and automatic run-time loop unravelling is described.This execution model Is based on queue machines that execute acyclic data-flow graphs.The use of separate instruction and data token spaces allows program reentrancy.Execution environments called contexts execute acyclic data-flow graphs associated with high-level code blocks.Iteration and function activation are implemented by the dynamic creation of contexts and do not require the use of tagged tokens.A multiprocessor architecture that supports this execution model is proposed.T~ system architecture is based on a partitioned ring in which each partition of the ring is a conventional processor/memory bus.The proposed architecture has bean simulated in software.A number of test programs have been developed and their execution on the proposed architecture has been evaluated.The performance of the proposed architecture with various numbers of processing elements is described.In addition, a number of task scheduling algorithms are presented and evaluated.

The performance of various access control protocols for bit-serial local area computer network (LACN) rings is studied. Applications in which mnessage packets are of fixed length and shorter than the total inherent propagation delay around the ring are the focus of attention. Token, slotted, and static and dynamic insertion rings are included in the study. In all cases, the transmitting station is responsible for removing its transmitted packet from the ring. Under this type of removal rule, it is possible for the stations of all types of ring structures to execute their access control algorithms with only a short fixed in-line delay in each station. The insertion rings dynamically switch longer delays (insertion registers) into the ring when they are transmitting a packet. The transmitter-remove rule operates in such a way that hogging of the ring transmission facility by a subset of stations cannot occur. Expressions that approximate average transfer time as a function of utilization are derived for all ring types and are checked by simulation. The expressions are found to be quite accurate at low ring utilization levels, which is the case of most importance for LACN's; but some of them exhibit significant errors at high utilization levels. For the assumed, short-packet environment, it is found that token rings exhibit the slowest transfer times, while dynamic insertion rings are fastest.

This paper describes the design of an arithmetic unit called CADAC (clean arithmetic with decimal base and controlled precision). Programming language specifications for carrying out "ideal" floating-point arithmetic are described first. These specifications include detailed requirements for dynamic precision control and exception handling, along with both complex and interval arithmetic at the level of a programming language such as Fortran or PL/I.

TORNET is an experimental local area computer network presently being designed and built in the Computer Group Laboratory of the Department of Electrical Engineering at the University of Toronto. The network consists of a number of local rings, each attached to a central ring. The local rings employ a variation on the slotted-ring format that uses a limited insertion technique to achieve reasonable response times for character traffic among many devices and small computers. Two fixed-length packet formats (one byte or 128 bytes of data) are used on the local rings. Only the longer format is used on the central ring which generally provides record level access to shared specialized equipment.

This paper considers access control for local area computer communication networks. We propose two distributed access control schemes for a bus network. The schemes are simple and asynchronous, and provide for collision-free communication among ports. In addition, one of the schemes provides a bounded, guaranteed time to transmisidon for each port. We also show that this scheme is efficient in the use of the bus bandwidth, in the sense that there is only a small fraction of time during which the bus is idle when there is at least one packet available for transmission.

This paper provides an analysis of the performance of an access control scheme recently proposed by Eswaran, Hamacher, and Shedler for a local bus network. The control scheme is simple and asynchronous, and provides for collision-free communication among ports of the network. It is also efficient in the use of the bus bandwidth, in the sense that there is only a small fraction of time during which the bus is idle when there is at least one packet available for transmission. The performance analysis emphasizes the characteristics of bus access response times at the individual ports.

Various possible implementation schemes for concurrent programming concepts are surveyed. Based upon this examination, computer design features are proposed which assist in the efficient realization of concurrent programming concepts in a multiprocessor machine which is constructed from a number of self-contained processors, each with its own random access memory. It is indicated how the proposed architecture provides hardware support for creating and terminating parallel execution paths. The hardware supports scheduled sharing of resources as its basic design feature. In particular, the problem of implementing scheduled waits in monitors is examined in detail. This is done in an environment where processes distributed among several physical processors are using a common monitor. It is also shown how the practical aspects of error resynchronization can be handled efficiently.

A proposal is presented for low level hardware features which would assist in the realisation of the abstraction of a computer system as a set of asynchronous communicating processes. A low level synchronisation and communication mechanism, called a mailbox, is described, together with details of a hardware structure for configuring a complete system around a set of these mailboxes. Programming for this architecture is then discussed. It is shown how the new features can be used for controlling input/output, and for handling general synchronisation.

This paper presents a method for correlating performance measures of small computers to design parameters. An experiment is described in which execution times and memory space requirements are gathered for three small benchmark kernels when run on fifteen small computers. The benchmarks are drawn from three different application areas. All of them exercise only the CPU ↔ memory area of the machines, and I/0 operations are not involved.Using standard regression analysis techniques, this data is then used to calculate coefficients in empirical equations which relate the performance measures, time and space, to easily quantifiable design parameters of the machines.

This book is intended (author's preface) as a suitable text for course B2 of Association for Computing Machinery Curriculum 1968 Recommendations. In general, the level of presentation is consistent with that intent. However, the book does not contain adequate material on all of the topics suggested in B2. For instance, micro-programming is very briefly discussed in three pages, and only two descriptive pages are provided on macros. There is also not enough discussion of selected programming techniques such as sorting, searching, scanning, text editing, arithmetic expression recognition, syntatic recognition, etc.

The main point made in the above comment, namely, that in our division array [1] only one row of the array is actively performing processing at any one time, is well taken. This leads to the reasonable conclusion that serially reusing a single row of logic, enabled by temporary storage of the partial remainder, leads to only a small (about 25 percent) speed degradation accompanied by substantial cost savings.

An augmented iterative array for binary division (IAD), is described. It uses carry-save reduction and carry-look-ahead principles to achieve high speed. Logic cost and speed comparisons with two other design techniques are presented. An 8-bit prototype model that operates in under 500 ns has been built from commercially available high-speed MSI TTL integrated circuits to verify the feasibility of the IAD scheme.

The logic cost and speed of parallel multipliers implemented in both binary and ternary logic is studied. Binary operand lengths of 8 through 32 bits and the corresponding ternary digit range of 6 through 21 are considered. For the particular design technique used, the binary versions are slightly faster where the speed criterion is in terms of the longest logic path from operands to product. Ternary designs show smaller total cost of gates and a major reduction in the number of required inputs, indicating greatly simplified wiring interconnection complexity.

A procedure is given for the construction of a von Neumann neighborhood iterative array to simulate a Moore neighborhood array in real time for the cases of up to three-dimensional arrays. The increase in the typical machine complexity accompanying this neighborhood complexity reduction is significantly less than that found in the general n-dimensional study of Cole [1].