Athas, William C., Seitz, Charles L. · Caltech Library · 1987
This report outlines the history, current status, current developments, and plans for the message-passing concurrent computers, or multicomputers, developed in the Submicron Systems Architecture Project at Caltech. These systems include the Cosmic Cube and its commercial descendants, two second-generation cosmic cubes currently in development, and the Mosaic C, a fine grain multicomputer whose nodes are single VLSI chips. Section 1 introduces the physical architectures, with particular attention to the characteristics of the message-passing networks. Section 2 describes the programming environments for the first and second generation medium grain size "cubes." Section 3 describes a fine grain concurrent object-oriented programming notation called Cantor, which currently runs on cubes and sequential systems, and which will be used for application programming of the Mosaic C.
Cited by 0Open access
Athas, William C., Seitz, Charles L. · CaltechAUTHORS (California Institute of Technology) · 1987
This report outlines the history, current status, current developments, and plans for the message-passing concurrent computers, or multicomputers, developed in the Submicron Systems Architecture Project at Caltech. These systems include the Cosmic Cube and its commercial descendants, two second-generation cosmic cubes currently in development, and the Mosaic C, a fine grain multicomputer whose nodes are single VLSI chips. Section 1 introduces the physical architectures, with particular attention to the characteristics of the message-passing networks. Section 2 describes the programming environments for the first and second generation medium grain size "cubes." Section 3 describes a fine grain concurrent object-oriented programming notation called Cantor, which currently runs on cubes and sequential systems, and which will be used for application programming of the Mosaic C.
Cited by 0Open access
David Padua, Amol Ghoting, John A. Gunnels et al. · 2011
Cited by 0
Siu-kit Wai, 衛兆傑 · 1996
Cited by 0
衛兆傑, Wai, Siu-kit · The HKU Scholars Hub (University of Hong Kong) · 1996
(Uncorrected OCR) \nAbstract of Thesis entitled 'Virtual Links for Multicomputers' Submitted by \n\nSiu Kit Wai \n\nfor the degree of \n\nMaster of Philosophy at Univsersity of Hong Kong in October 1996 \n\nIn order to increase computation power, multiple autonomous computers or processors are connected to form a multicomputer. The performance boost is the result of exploiting in parallel the processing power available in individual processors. Parallel processing, however, requires the cooperation among the processors, which implies interprocessor communication. The efficiency of such communications is limited by the bandwidth and number of communication channels between directly connected processors. \n\nMultiple processes on a processor share a few hardware communication links/channels to communication with processes executing on a different processor. Effective and efficient sharing of channels is important for the overall system performance; hence it is important that the sharing be properly managed. When the sharing is not provided by the hardware, it can be provided in software at system level. Without a managing component, processes need to be programmed to flight for and gain exclusive access to the communication links. This is usually not effective, error-prone, and could reduce the overall performance of processes executing in the processor. \n\nFlexibility is a main advantage of providing a channel-sharing mechanism at system level. Parameters such as packet size, and configuration of the system can be customized and tuned to meet the communication characteristics of different applications. \n\nIn this project, we investigate how link sharing can be provided at system level. Our approach is based on idea of virtual links. The system is designed to be as transparent and easy to be used as possible. We will discuss how different \n\nparameters and configurations affect the system functionality and performance. We also compare this software solution to other existing solutions including a hardware solution. \n\nii
Cited by 0
Gavin Constantine Michael · ANU Open Research (Australian National University) · 1996
This thesis considers problems in process and data partitioning when compiling programs for distributed-memory parallel computers (or multicomputers). These partitions may be specified by the user through the use of language constructs, or automatically determined by the compiler. Data and process partitioning techniques are developed for two models of compilation. The first compilation model focusses on the loop nests present in a serial program. Executing the iterations of these loop nests in parallel accounts for a significant amount of the parallelism which can be exploited in these programs. The parallelism is exploited by applying a set of transformations to the loop nests. The iterations of the transformed loop nests are in a form which can be readily distributed amongst the processors of a multicomputer. The manner in which the arrays, referenced within these loop nests, are partitioned between the processors is determined by the distribution of the loop iterations. The second compilation model is based on the data parallel paradigm, in which operations are applied to many different data items collectively. High Performance Fortran is used as an example of this paradigm. Novel collective communication routines are developed, and are applied to provide the communication associated with the data partitions for both compilation models. Furthermore, it is shown that by using these routines the communication associated with partitioning data on a multicomputer is greatly simplified. These routines are developed as part of this thesis. The experimental context for this thesis is the development of a compiler for the Fujitsu AP1000 multicomputer. A prototype compiler is presented. Experimental results for a variety of applications are included.
Cited by 0Open access
Sanjay Ranka, Sartaj Sahni · 1990
Convolution is an important primitive in computer vision and image processing. In this paper, we present an efficient algorithm for convolution on a mesh connected computer with wraparound. Our algorithm does not require a broadcast feature for data values as assumed by previously proposed algorithms. As a result, the algorithm is applicable both to SIMD as well as MIMD meshes. For an NN image and a MM template, the previous algorithms take O (M q) time on an NN mesh connected multicomputer (q is the number of bits in each entry of the convolution matrix). Our algorithms have complexity O (M r) where r = max {number of bits in an image entry, number of bits in a template entry}. So, in addition to not requiring a broadcast capability, our algorithms are faster for binary images.
Cited by 0
Microelectronics Reliability · 1990
Cited by 1
J. Kim, Chita R. Das, Wei-Ming Lin et al. · IEEE Transactions on Reliability · 1989
An analytic model for the reliability evaluation of hypercube multicomputers is presented. The model is based on the decomposition principle, where a hypercube of a higher dimension is recursively decomposed into smaller hypercubes, until the reliability of the smallest cube is modeled exactly. The reliability of the large n-cube is then obtained from this smallest base model using a recursive equation. The reliability model used is task-based, i.e., it is assumed that the system is operational if a task can be executed on the system. Analytic results are given for n-dimensional hypercubes with up to 75% system degradation. The model is validated by comparison of analytic results with simulation results.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 37
Cesar Augusto Fonticielha De Rose, Hans Ulrich Heiss, Philippe Olivier Alexander Navaux · PUCRS Repository (Pontifical Catholic University of Rio Grande do Sul) · 2000
Current processor allocation techniques for multicomputers are based on centralized front-end based algorithms. As a result, the applied strategies are usually restricted to static, contiguous, structure preserving allocation, and suffer from low parallelism and weak fault tolerance. To lift these restrictions we are investigating a distributed approach to the processor allocation problem for mesh interconnected distributed memory machines. We conducted several experiments, some simulated and some running over a Simens hpcLine Primergy Server with 96 nodes, which showed that distributed allocation is feasible with current technologies.
Cited by 0Open access
Xiaoxiang Sun, H. Zhang, Lionel M. Ni · IEEE Transactions on Computers · 1992
Three parallel algorithms, namely, the parallel partition LU (PPT) algorithm, the parallel partition hybrid (PPH) algorithm, and the parallel diagonal dominant (PDD) algorithm, are proposed for solving tridiagonal linear systems on multicomputers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and nonpivoting. The PPT algorithm is good when the number of processors is small; otherwise, the PPH algorithm is better. When the system is diagonal dominant, the PDD algorithm is highly parallel and provides an approximate solution which equals the exact solution within machine accuracy. Computation and communication complexities of the three algorithms are presented. All three methods have been implemented on a 64-node nCUBE-1 multicomputer. The analytic results closely match the results measured from the nCUBE-1 machine.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 46
Mendes, Celso Luiz · 1997
Despite the performance potential of multicomputers, several factors have limited their widespread adoption. Of these, performance variability is among the most significant. Execution of some programs may yield only a small fraction of peak system performance, whereas others approach the system's theoretical performance peak. Moreover, the observed performance may change substantially as application program parameters vary. Data parallel languages, which facilitate the programming of multicomputers, increase the semantic distance between the program's source code and its observable performance, thus aggravating the performance problem. In this thesis, we propose a new methodology to predict the performance scalability of data parallel applications on multicomputers. Our technique represents the execution time of a program as a symbolic expression that is a function of the number of processors (P), problem size (N), and other system-dependent parameters. This methodology is based on information collected at compile time. By extending an exiting data parallel compiler (Fortran D95), we derive, during compilation, a symbolic model that represents the cost of each high-level program section and, inductively, of the complete program. These symbolic expressions may be simplified externally with current symbolic tools. Predicting performance of the program for a given pair (P,N) requires simply the evaluation of its corresponding cost expression. We validate our implementation by predicting scalability of a variety of loop nests, with distinct computation and communication patterns. To demonstrate the applicability of our technique, we present a series of concrete performance problems where it was successfully employed: prediction of total execution time, identification and tracking of bottlenecks, cross-system prediction, and evaluation of code transformations. These examples show that the technique would be useful both to users, in optimizing and tuning their programs, and to advanced compilers, which would have a means to evaluate the expected performance of a synthesized code. According to the results of our study, by integrating compilation, performance analysis and symbolic manipulation tools, it is possible to correctly predict, in an automated fashion, the major performance variations of a data parallel program written in a high-level language. RESUMO: Apesar do potencial de desempenho dos multicomputadores, vários fatores limitaram sua adoção generalizada. Destes, a variabilidade de desempenho está entre as mais significativas. A execução de alguns programas pode render apenas uma pequena fração do desempenho do sistema de pico, enquanto outros se aproximam do pico de desempenho teórico do sistema. Além disso, o desempenho observado pode mudar substancialmente à medida que os parâmetros do programa de aplicação variam. Linguagens paralelas de dados, que facilitam a programação de multicomputadores, aumentam a distância semântica entre o código fonte do programa e seu desempenho observável, agravando assim o problema de desempenho. Nesta tese, propomos uma nova metodologia para prever a escalabilidade de desempenho de aplicações paralelas de dados em multicomputadores. Nossa técnica representa o tempo de execução de um programa como uma expressão simbólica que é uma função do número de processadores (P), tamanho do problema (N) e outros parâmetros dependentes do sistema. Esta metodologia baseia-se em informações coletadas em tempo de compilação. Ao estender um compilador paralelo de dados de saída (Fortran D95), derivamos, durante a compilação, um modelo simbólico que representa o custo de cada seção de programa de alto nível e, indutivamente, do programa completo. Essas expressões simbólicas podem ser simplificadas externamente com ferramentas simbólicas atuais. Prever o desempenho do programa para um determinado par (P, N) requer simplesmente a avaliação da sua correspondente expressão de custo. Nós validamos nossa implementação, prevendo escalabilidade de uma variedade de ninhos de loop, com padrões de computação e comunicação distintos. Para demonstrar a aplicabilidade de nossa técnica, apresentamos uma série de problemas de desempenho concreto onde foi empregado com sucesso: previsão do tempo de execução total, identificação e rastreamento de estrangulamentos, previsão de sistemas cruzados e avaliação de transformações de código. Esses exemplos mostram que a técnica seria útil tanto para os usuários, otimizando e afinando seus programas, quanto para os compiladores avançados, o que teria um meio de avaliar o desempenho esperado de um código sintetizado. De acordo com os resultados do nosso estudo, através da integração de ferramentas de compilação, análise de desempenho e manipulação simbólica, é possível prever corretamente, de forma automatizada, as principais variações de desempenho de um programa paralelo de dados escrito em linguagem de alto nível.
Cited by 0
José A. Gallud, José M. García, Francisco J. Quiles · 2007
Formal Methods and Techniques are widely used in communication systems and distributed computing. Today, such techniques are not sufficiently employed in other systems as industrial processes or hardware design. In this paper we propose a methodology to apply the Lotos technique in computer design. Thus, we describe a particular case based on specifying a classical router algorithm in massively parallel machines. The e-cube routing is a deadlock-free algorithm which serves as a valid reference for our purpose. Lotos tools are used to validate the system, in particular we have used LOLA for analysis and design testing. 1: Specifying Computer Behaviour Using Lotos A number of advantages have been attributed to the use of formal specifications. These advantages cover from enhanced insight into and understanding of specifications, up to help in verification of the specifications and their implementations. Formal methods are intended to be used by software and hardware designers to describe systems, and in particular, to verify that the system has the desired properties [19].
Cited by 0
Andy D. Pimentel, L.O. Hertzberger · 2002
The large design space of modern computer architectures calls for performance modelling tools to facilitate the evaluation of different alternatives. In this paper we give an overview of the Mermaid multicomputer simulation environment. This environment allows the evaluation of a wide range of architectural design tradeoffs while delivering reasonable simulation performance. To achieve this, simulation takes place at a level of abstract machine instructions rather than at the level of real instructions. Moreover, a less detailed mode of simulation is also provided. So when accuracy is not the primary objective, this simulation mode can yield high simulation efficiency. As a consequence, Mermaid makes both fast prototyping and accurate evaluation of multicomputer architectures feasible.
Cited by 11
Xiaola Lin, Lionel M. Ni · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 1990
Cited by 15
2008
The large design space of modern computer architectures calls for performance modelling tools to facilitate the evaluation of different alternatives. In this paper, we give an overview of the Mermaid multicomputer simulation environment. This environment allows for the evaluation of a wide range of architectural design tradeoffs while delivering good simulation performance. To achieve this, simulation takes place at a level of abstract machine instructions rather than at the level of real instructions. Moreover, a less detailed mode of simulation is also provided. So when accuracy is not the primary objective, this simulation mode can yield high simulation efficiency. As a consequence, Mermaid makes both fast prototyping and accurate evaluation of multicomputer architectures feasible. 1
Cited by 0
Narain Gehani · Computer Languages · 1982
Cited by 3
Andrew Tanenbaum Henri, Henri E. Bal, M. Frans Kaashoek · 1993
Cited by 0
Bénédicte Herrmann, Laurent Philippe · Lecture notes in computer science · 1991
Cited by 1
Domingo Giménez, Vicente Hernández, Antonio M. Vidal · Lecture notes in computer science · 1996
Cited by 0