206034930
Performance Evaluation of a Workstation Cluster, TMC CM-5, and Intel Paragon/XP Using a Parallel Homology Analysis Program
Abstract In the homology analysis, required memory size and computing time proportionally increase with the square of the number of amino acids in protein. In order to expand the limit of size and to carry out analysis effectively, we parallelized for homology analysis program adopting the wavefront method with tiling. The performance of a workstation cluster, CM5, and Paragon was compared by using our program. For performance evaluation of these machines, we have made a model of our parallel homology analysis computation. Using the model, we can understand the characteristics of these machines with respect to our program. Execution time estimated by the execution model is in good agreement with the observation. The averaged error of the estimation to the observation on a workstation cluster, CM5, and Paragon are 0.1%, 5%, and 2%. Almost linear speed-up has been observed from 1PU to 20PUs on them. The ratio of the performance of Paragon, CM5, and the workstation cluster is 1:0.38:0.22. This ratio is constant to the variety of the size of problem and the number of processors.
31888240
Performance Improvement by Data Management Layer in a Grid RPC System
A grid RPC system provides a useful and intuitive programming interface for master-worker type applications in a grid environment. In many grid applications, such as parameter search programs, both master and workers are often required to have a large amount of common data. Since in the RPC model the data must be transferred from the master directly to each worker, the master is sometimes a bottleneck, resulting in poor performance. In order to improve the performance in such cases, we propose a model to decouple the data transfer by a data management layer from the RPC programming. We have designed and implemented a prototype data transfer layer called OmniStorage to OmniRPC, which is a grid RPC system for parallel programming in a grid environment. This allows efficient data transmission of a large amount of data by placing intermediate relay servers, taking the network topology into account, to route the communication and cache the common data in the server. We have evaluated the performance of the proposed system by using synthetic workloads and a real grid application. The results show that OmniStorage can improve the performance of OmniRPC applications compared to the case of using only OmniRPC.
206591385
A Parallel Method for Large Sparse Generalized Eigenvalue Problems by OmniRPC in a Grid Environment
In this paper we present a parallel method for finding several eigenvalues and eigenvectors of a generalized eigenvalue problem Ax = λBx, where A and B are large sparse matrices. A moment-based method by which to find all of the eigenvalues that lie inside a given domain is used. In this method, a small matrix pencil that has only the desired eigenvalues is derived by solving large sparse systems of linear equations constructed from A and B. Since these equations can be solved independently, we solve them on remote hosts in parallel. This approach is suitable for master-worker programming models. We have implemented and tested the proposed method in a grid environment using a grid RPC (remote procedure call) system called OmniRPC. The performance of the method on PC clusters that were used over a wide-area network was evaluated.
280911
Multiple instruction streams in a highly pipelined processor
In a highly pipelined processor, instruction dependencies involving both and control information often limit its potential performance. A cyclic pipeline machine allows multiple instruction streams to share these pipeline stages in time to remove the data and control dependencies. These multiple instruction streams exploit more parallelism in parallel programs. It provides an alternative architectural solution for new technologies such as GaAs and Josephson logic device, which prefer a highly pipelined architecture. The authors define the basic model of a cyclic pipeline machine, and examine the performance improvement of various configurations of cyclic pipeline machines compared to the same degree of pipelining of a conventional pipelined processor. The simulation results indicate that pipelining in the individual instruction streams increases the performance to maximize the utilization of resources in a highly pipelined processor.<<ETX>>
813995
Experience with fine-grain communication in EM-X multiprocessor for parallel sparse matrix computation
Sparse matrix problems require a communication paradigm different from those used in conventional distributed-memory multiprocessors. We present in this paper how fine-grain communication can help obtain high performance in the experimental distributed-memory multiprocessor, EM-X, developed at ETL, which can handle fine-grain communication very efficiently. The sparse matrix kernel, Conjugate Gradient, is selected for the experiments. Among the steps in CG is the sparse matrix vector multiplications we focus on in the study. Some communication methods are developed for performance comparison, including coarse-grain and fine-grain implementations. Fine-grain communication allows exact data access in an unstructured problem to reduce the amount of communication. While CG presents bottlenecks in terms of a large number of fine-grain remote reads, the multithreaded principles of execution is so designed to tolerate such latency. Experimental results indicate that the performance of fine-grain read implementation is comparable to that of coarse-grain implementation on 64 processors. The results demonstrate that fine-grain communication can be a viable and efficient approach to unstructured sparse matrix problems on large-scale distributed-memory multiprocessors.
16491780
Performance evaluation of OmniRPC in a grid environment
OmniRPC is a Grid RPC system for parallel programming in a grid environment. In order to understand the performance characteristics of OmniRPC, we executed a synthetic benchmark program which varies the execution time in remote nodes and the amount of communication on several configurations of our grid environment. The result shows the performance of the application is improved if RPC data transmissions are less than 10 KB, the job time in remote nodes is more than 4 seconds, and RPCs are called more than 256 times. Our result also shows a small performance degradation when using the feature of communication multiplexing. We also measured the performance of the EP application from the NAS parallel benchmark suite. In EP, even if using SSH or the Globus GRAM as methods of agent invocation, both performances are almost the same. As a practical application, we parallelized the CONFLEX molecular confirmation search program using OmniRPC. In the comparison of CONFLEX-G with the CONFLEX MPI version, CONFLEX-G achieves comparable efficiencies to the MPI version and increased speed by using two or more clusters.
8686702
Theory of Judgments and Derivations
We propose a computational and logical framework NF (Natural Framework) which is suitable for presenting mathematics formally. Our framework is an extendable framework since it is open-ended both computationally and logically in the sense of Martin-Lof's theory or types. NF is developed in three steps. Firstly, we introduce a theory of expressions and schemata which is used to provide a universe for representing mathematical objects, in particular, judgments and derivations as well as other usual mathematical objects. Secondly, we develop a theory of judgments within the syntactic universe of expressions. Finally, we introduce the notions of derivation and derivation game and will show that we can develop mathematics as derivation games by regarding mathematics as an open-ended process of defining new concepts and deriving new judgments. Our theory is inspired by Martin-Lof's theory of expressions and Edinburgh LF, but conceptually much simpler. Our theory is also influenced by Gentzen's natural deduction systems.
28509315
Development of a method to construct three-dimensional finite element models of thoracic aortic aneurysms from MRI images
Most patients die when thoracic aortic aneurysms rupture. In order to avoid the ruptures, the aneurysms are replaced with aortic prostheses when their maximum diameter exceeds 5 cm. Because this criterion is based on the experiences, some aneurysms rupture even if the diameters are smaller than this criterion. To treat the aneurysm properly, it is necessary to find out the new criterion. The rupture is thought to have a close relationship with the stress in the wall. Hence, there is much research about the stress, but this research uses the straight tube model. The model shape does not seem appropriate to a thoracic aorta shape. Hence, we developed the method to construct three-dimensional finite element models of thoracic aortic aneurysms from MRI images.
27739305
Explicit Environments
We introduce λƐ, a simply typed calculus with environments as first class values. As well as the usual constructs of λ and application, we have e[[a]] which evaluates term a in an environment e. Our environments are a set of variable-value pairs, but environments can also be computed by function application and evaluation in some other environments. The notion of environments here is a generalization of explicit substitutions and records. We show that the calculus has desirable properties such as subject reduction, confluence, conservativity over the simply typed λβ-calculus and strong normalizability.
46610662
CAL: A Computer Assisted Learning System for Computation and Logic
In this paper, we describe a computer system CAL which assists students' understanding of a lecture course in logic and computation. We introduce a new foundational theory of expressions, which is inspired by the theory of expressions due to Martin-Lof [6], and use the expressions determined by the theory to implement various syntactic objects in CAL. We also introduce the concept of derivation game, and show that various logical and computational systems given in the lecture course can be defined uniformly by derivation games.
27411446
A Purely Functional Language with Encapsulated Assignment
We introduce a new functional programming language with assignment. The language, which we call Λ, is a conservative extension of the λβ-calculus, and as such it it a higher order functional language in which we can manipulate functions as first class objects. Λ has a lazy evaluation semantics and Λ programs can be evaluated in parallel. Λ also supports imperative programming in terms of assignments. All the assingments in Λ are encapsulated within suitable scope of the let constructs. The language is therefore side-effect free and referentially transparent. We show by an example that we can smoothly reason about Λ programs.