No abstract available.

The simulation of parallel computers is discussed. In particular, a technique, called cross-profiling, that can be used to improve the efficiency of these simulations substantially is presented and evaluated. Cross-profiling, along with another simulation technique called execution-driven simulation, can be used to simulate one processor's instruction set (the target processor) with another processor that has a different instruction set (the host processor). Moreover, this technique is significantly faster than the usual method where several host instructions are executed to emulate the effect of executing a single instruction of the target processor. The cross-profiling technique is introduced, and it is shown how it can be combined with execution-driven simulation. The results of several experiments that demonstrate that the error introduced by cross-profiling is typically less than 1% are presented.>

Article Free Access Share on The rice parallel processing testbed Authors: R. C. Covington Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile , S. Madala Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile , V. Mehta Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile , J. R. Jump Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile , J. B. Sinclair Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile Authors Info & Claims SIGMETRICS '88: Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systemsMay 1988 Pages 4–11https://doi.org/10.1145/55595.55596Online:01 May 1988Publication History 87citation426DownloadsMetricsTotal Citations87Total Downloads426Last 12 Months13Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper presents and evaluates a class of buffered interconnection networks which provide performance and cost levels intermediate to a bus and a delta network. These networks, referred to as hybrid networks, are formed by beginning with a delta network and substituting buses for the final stages of the network. The choice of the number of stages replaced determines the bandwidth of the network. The reduction of network bandwidth is accompanied by a corresponding reduction in network cost. Hybrid networks provide the system architect with a cost-effective solution to design problems in which the required interconnection bandwidth is greater than that of a bus but less than that of a full delta network.

The degree to which high-speed vector processors approach their peak performance levels is closely tied to the amount of interference they encounter while accessing vectors in memory. In this paper we present an evaluation of a storage scheme that reduces the average memory access time in a vector-oriented architecture. A skewing scheme is used to map vector components into parallel memory modules such that, for most vector access patterns, the number of memory conflicts is reduced over that observed in interleaved parallel memory systems. Address and data buffers are used locally in each module so that transient nonuniformities which occur in some access patterns do not degrade performance. Previous investigations into skewing techniques have attempted to provide conflict-free access for a limited subset of access patterns. The goal of this investigation is different. The skewing scheme evaluated here does not eliminate all memory conflicts but it does improve the average performance of vector access over interleaved systems for a wide range of strides. It is shown that little extra hardware is required to implement the skewing scheme. Also, far fewer restrictions are placed on the number of memory modules in the system than are present in other proposed schemes.

This paper presents and evaluates a scheme for reducing the average memory access time in a vector processing architecture. This scheme uses data skewing to distribute vectors among the modules of a parallel memory system in such a way that, for typical vector access patterns, the average number of memory conflicts is reduced. It also employs both address and data buffers in each module to smooth out the transient irregularities that occur in some vector access patterns. Most previous data skewing techniques were developed to provide conflict-free access for a limited set of access strides. While the proposed scheme does not eliminate all conflicts, it improves the average performance over non-skewed parallel memories by significantly reducing the number of conflicts for a wide range of strides. Also, this effect is much less dependent on the number of memory modules than the skewing schemes used to obtain conflict-free access.

The throughput of unbuffered shuffle-exchange networks (also known as delta networks) is related to the arrival rate by a quadratic recurrence relation. Lower and upper bounds on the solution of this recurrence relation are derived in this paper. Two approaches for improving the throughput of unbuffered delta networks are investigated. The first approach combines multiple delta subnetworks of size N × N each, in parallel, to obtain a network of size N × N. Three policies used to distribute the incoming packets between the subnetworks are discussed and the relative effect of each on the throughput is compared. The second approach replaces each link of the simple delta networks by K parallel links (K equals 2,4,...,). The throughput of such networks is analyzed and one possible implementation for crossbar switches that could be used in these networks is discussed. The throughput of such networks with four parallel links is almost equal to the throughput of crossbars.

article Free Access Share on Matrix multiplication in an interleaved array processing architecture Authors: G. Wolf Department of Electrical and Computer Engineering, Rice University, Houston Texas Department of Electrical and Computer Engineering, Rice University, Houston TexasView Profile , J. R. Jump Department of Electrical and Computer Engineering, Rice University, Houston Texas Department of Electrical and Computer Engineering, Rice University, Houston TexasView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 11–17https://doi.org/10.1145/327070.327112Published:01 June 1985Publication History 0citation253DownloadsMetricsTotal Citations0Total Downloads253Last 12 Months56Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This correspondence investigates some methods for improving the performance of single-stage shuffle-exchange networks (SSN's) in a packet communication environment where the modules in a computer system communicate by sending fixed size packets. The three new switching strategies proposed use extra buffers to enhance performance, while preventing deadlocks. An intuitive criterion for determining the applicability of approximate analysis techniques is discussed.

This paper investigates some methods for improving the performance of Single Stage Shuffle Exchange Networks (SENs) and Multistage Interconnection Networks (MINs). The three new switching strategies proposed use extra buffers to enhance performance. Approximate analysis and simulation results indicate significant improvement in performance for both SENs and MINs. An intuitive method for determining the applicability of the approximate analysis is discussed and some performance measures, which should be useful in evaluating the performance of networks are defined.

Delta networks are a class of multistage interconnection networks with gate complexity less than crossbar switches that are easy to control, and which include several networks that have been proposed in the literature as special cases. Buffered delta networks have queues of packets between the stages of the network. This paper presents analytic and simulation results for the performance of delta networks in a packet communication environment. The performance of buffered delta networks is compared with unbuffered delta networks and crossbar switches. It is demonstrated that buffering produces considerable improvement in the performance of these networks, making their performance comparable to that of crossbar switches.

This paper presents quantitative techniques for the evaluation and comparison of pipelined digital systems. They are based on three measures of effectiveness: delay, average time/operation, and average cost/operation. Moreover, the techniques do not assume that there is an unbounded stream of operations to be performed, although this case is considered. The use of the analysis methods to compare different ways of pipelining a given algorithm is illustrated by an investigation of the pipelining of general four-neighbor cellular arrays. The methods can also be used to evaluate different algorithms for performing the same operation. This is illustrated by comparing three array algorithns for integer multiplication.

This paper presents a parallel memory scheme suited for pipelined processing units. The scheme is shown to be modular, relatively low cost and flexible. The scheme allows an arbitrary number of variables in the vector operations. It is shown that data alignment is handled by a simple interconnection scheme and that the interconnection scheme can be implemented in the memory modules. It is shown that the scheme facilitates efficient implementation of the Perfect Shuffle interconnection, hence the implementation of parallel algorithms using that interconnection scheme.

The paper is concerned with a class of control systems which can be represented by a graphical model called an MG-control system (MGCS) In particular, the closure propertms of thin class are studmd More precisely, this paper presents necessary and sufficmnt conditions for the compomte system, obtained by interconnecting two of these systems, to be represented as an MGCS.These results are then extended to networks composed of several interconnected control systems.In solwng this problem, it is shown that whenever the lnterconnectmn of two or more systems results m a system that is not representable as an MGCS, it m due to the presence of "deadlock" in the composite system.Hence the results of the paper provide a means of detecting deadlock in a network of control systems.

This paper introduces a class of programmable cellular arrays, called control arrays, and presents a technique for programming these arrays to realize asynchronous control systems. Control arrays are two-dimensional uniform networks composed of a collection of identical cells that can be independently programmed to one of two internal states. A control system is a device that controls one or more operations by means of initiation and termination signals that are transmitted through bidirectional control links. A control system model is developed by augmenting the marked graph model in order to represent constraints on the generation of these control signals. Finally, an array synthesis procedure for realizing control systems with control arrays is presented.

This paper is concerned with the problem of detecting when two asynchronous control systems are equivalent. The systems investigated in the paper are first represented by means of a formal model called an asynchronous control structure (ACS). This model specifies the constraints imposed on the generation of control signals by a system by means of a simple graphical model called a marked graph. Behavioral equivalence is then characterized in terms of the set of all possible sequences of control signals that can be generated by the system. These sequences are represented by means of another (infinite) marked graph, called a behavior graph. Finally, it is shown that two control systems are equivalent if and only if their behavior graph representations have identical (finite) generating sets.

The logical organization of a programmable cellular array is presented and discussed. This array is a two-dimensional array of identical cells, each of which can be programmed to one of 12 functional states. It is shown that by appropriate selection of the cell states, a useful class of microprograms can be realized with the array. The realization of a microprogram consists of two steps. First, each of the microinstructions of the program are implemented in a row of the array. Second, the control structure of the microprogram is realized by using some of the cells at the left end of each row to generate the control signals for the row.

This paper is concerned with techniques for the synthesis of binary output synchronous sequential machines. In particular, the proposed techniques can be used to realize such a machine as an interconnection of a finite set of identical two-state component machines or modules. Furthermore, the module can be selected in advance since it depends only on the number of inputs and not on the structure of the machine to be realized.