bluuebunny/crossref_metadata_2025_split huggingface dataset:
Porting a dusty deck Fortran program to a shared‐memory multiprocessor
Authors: Beavis Andy , Phillips Chris 
Published: November 2006

AbstractWe describe an attempt to improve the performance of a sequential Fortran code on a shared memory multiprocessor. The only parallelism employed is that provided by a set of parallel BLAS. The code is modified to make maximum use of the BLAS and, in particular, to use an appropriate LAPACK routine. Comparisons are made with automatically generated parallel code.
Parallel language developments in Europe: An overview
Authors: Perrott R. H. 
Published: November 2006

AbstractThis article is concerned with the topic of parallel programming language design and implementation, with particular emphasis on the developments which are, and have been, taking place in Europe. Consideration is given to specific approaches to parallel programming with illustrative examples taken from projects which have been carried out in Europe. The paper is based on a report prepared for the European Commission during 1990.
Parallel distributed seismic migration
Authors: Almasi G. S. , Hale D. , McLuckie T. , Bell J. , Gordon A. 
Published: November 2006

AbstractWe report significant speed‐up for seismic migration running in parallel on networkconnected IBM RISC/6000 workstations, A sustained performance of 15 MFLOP is obtained on a single‐entry‐level model 320, and speed‐ups as high as 5 are obtained for six workstations connected by Ethernet or token ring. Our parallel software uses remote procedure calls provided by NCS (Network Computing System). We have run over a dozen workstations in parallel, but speed‐ups become limited by network data rate. Fiber‐optic communication should allow much greater speed‐ups, and we describe our preliminary results with the fiberoptic serial link adapter of the RISC/6000. We also present a simple theoretical model that agrees well with our measurements and allows speed‐up to be predicted from a knowledge of the ratio of computation to communication, which can be determined empirically before the program is parallellzed. We conclude with a brief discussion of alternative software approaches and programming models for network‐connected parallel systems. In particular, our program was recently ported to PVM and Linda, and preliminary measurements yield speed‐ups very close to those described here.
Experience with multi‐transputer Ada
Authors: Bishop Judy M. , Thomas Ken S. 
Published: November 2006

AbstractThe transputer is one of the most cost‐effective multicomputer components to buy, but still one of the hardest to program. Even if the parts of a program that are destined for individual transputers are programmed in a familiar high‐level language (Ada or Fortran or C), users are forced to be aware of occam when connecting transputers together with harnesses. Moreover, the design of parallel and distributed algorithms is in itself a challenging field. This paper describes experience with using the Alsys Ada compiler on single and multiple transputer configurations, and considers whether Ada makes it any easier to gain access to the power of multi‐transputers. Early performance figures indicate that Ada running on transputer arrays compares favourably with the speed of other languages. An assessment of the impact of the proposed Ada 9X support for distribution is made.
Kernel‐Kernel communication in a shared‐memory multiprocessor
Authors: Chaves Eliseu M. , Das Prakash Ch. , Leblanc Thomas J. , Marsh Brian D. , Scott Michael L. 
Published: November 2006

AbstractIn the standard kernel organization on a bus‐based multiprocessor, all processors share the code and data of the operating system; explicit synchronization is used to control access to kernel data structures. Distributed‐memory multicomputers use an alternative approach, in which each instance of the kernel performs local operations directly and uses remote invocation to perform remote operations. Either approach to interkernel communication can be used in a large‐scale shared‐memory multiprocessor.In the paper we discuss the issues and architectural features that must be considered when choosing between remote memory access and remote invocation. We focus in particular on experience with the Psyche multiprocessor operating system on the BBN Butterfly Plus. We find that the Butterfly architecture is biased towards the use of remote invocation for kernel operations that perform a significant number of memory references, and that current architectural trends are likely to increase this bias in future machines. This conclusion suggests that straightforward parallelization of existing kernels (e.g. by using semaphores to protect shared data) is unlikely in the future to yield acceptable performance. We note, however, that remote memory access is useful for small, frequently‐executed operations, and is likely to remain so.
Levels of atomic action in the Flagship parallel system
Authors: Mayes K. R. , Keane J. A. 
Published: November 2006

AbstractThe Flagship system is a graph reduction machine having a distributed physical architecture. Although Flagship sits firmly in the declarative world, explicit state is supported to express the behaviour of the operating system. This state not only has to be isolated from the declarative aspects of the Flagship machine, but also has to be supported with respect to distribution. The mechanisms provided for maintaining consistency of state are discussed with respect to atomic actions at levels in the Flagship system. This approach is used to demonstrate how the software environment was supported by the basic execution mechanism of the machine. The nature, construction and creation of system software components are described and the structure of the system software is discussed with particular reference to optimising access to distributed resources.
Region‐to‐region visibility analysis using data parallel machines
Authors: Teng Y. Ansel , Dementhon Daniel , Davis Larry S. 
Published: November 2006

AbstractWe propose an algorithm for solving region‐to‐region visibility problems on digital terrain models using data parallel machines. Since global communication is the bottleneck in this kind of algorithm, the algorithm we propose focuses on the reduction of global communication. The algorithm analyses a strip of the source region at a time and sweeps through the source strip by strip. At most four sweeps are needed for the analysis. By exploring the coherence properties in the processor structure, global communication is minimized and complexity is substantially improved. Furthermore, all global write operations are exclusive and concurrency in global read operations is minimized. Since the problem size is usually large, we also designed rules of decomposition to efficiently handle the cases where the required number of processors is greater than available. The algorithm has been implemented on a Connection Machine CM‐2, and results of computational experiments are presented.
Pyramid mappings onto hypercubes for computer vision: Connection machine comparative study
Authors: Ziavras Sotirios G. , Siddiqui Muhammad A. 
Published: November 2006

AbstractThe paper presents a comparative analysis for algorithms that map pyramids onto hypercubes. The analysis is based on some important performance measures from graph theory and actual results from a Connection Machine system CM‐2 containing 16K processors. Connection Machine results are presented for pyramid algorithms that compute the perimeter of objects, apply 2‐dimensional convolution, and segment images.
Macromolecular electron density averaging on distributed memory MIMD systems
Authors: Marinescu Dan C. , Rice John R. , Cornea‐Hasegan Marius A. , Lynch Robert E. , Rossmann Michael G. 
Published: November 2006

AbstractThe paper discusses algorithms and programs for electron density averaging using a distributed memory MIMD system. Electron density averaging is a computationally intensive step needed for phase refinement and extension in the computation of the 3‐D structure of macromolecules like proteins and viruses. The determination of a single structure may require thousands of hours of CPU time for traditional supercomputers. The approach discussed in this paper leads to a reduction by one to two orders of magnitude of the computing time. The program runs on an Intel iPSC/860 and on the Touchstone Delta system and uses a user controlled shared virtual memory and a dynamic load‐balancing mechanism.
Dependence analysis for outer loop parallelization of existing Fortran‐77 programs
Authors: Stein Josef , Fox Geoffrey C. 
Published: November 2006

AbstractWe have used six static parallelization tools on four Fortran‐77 programs used in physics simulations. We indicate areas where current tools have difficulties in recognizing parallelism, and illustrate these issues with simple examples. We suggest that a dynamic dependency analysis tool is needed to aid the user in the parallelization of dusty decks.
Experiments with Program unification on the Cray Y‐MP
Authors: Chuang Ling‐Yu , Rego Vernon , Mathur Aditya 
Published: November 2006

AbstractProgram unification is a technique for source‐to‐source transformation of code for enhanced execution performance on vector and SIMD architectures. This work focuses on simple examples of program unification to explain the methodology and demonstrate its promise as a practical technique for improved performance. Using simple examples to explain how unification is done, we outline two experiments in the simulation domain that benefit from unification, namely Monte Carlo and discrete‐event simulation. Empirical tests of unified code on a Cray Y‐MP multiprocessor show that unification improves execution performance by a factor of roughly 8 for given application. The technique is general in that it can be applied to computation‐intensive programs in various data‐parallel application domains.
A parallel block row‐action method for solving large sparse linear systems on distributed memory multiprocessors
Authors: D'apuzzo Marco , De Rosa Maria Assunta 
Published: November 2006

AbstractRecently developed block‐iterative versions of some row‐action algorithms for solving general systems of sparse linear equations allow parallelism in the computations when the underlying problem is appropriately decomposed. However, problems associated with the parallel implementation of these algorithms have to be addressed.In this paper we present an implementation on distributed memory multiprocessors of a block version of the Kaczmarz row‐action method. One of the main issues related to the efficient implementation of this method on a concurrent environment is to develop suitable communication schemes in order to reduce the amount of communication needed at each iteration.We propose two data distribution strategies which lead to different computation and communication schemes.To verify and compare the effectiveness of the proposed strategies, numerical experiments have been carried out on a Symult S2010 and a Meiko Computing Surface. The performance evaluation has been done using a scaled efficiency model.
Allocating data to distributed‐memory multiprocessors by genetic algorithms
Authors: Mansour Nashat , Fox Geoffrey C. 
Published: November 2006

AbstractWe present three genetic algorithms (GAs) for allocating irregular data sets to multiprocessors. These are a sequential hybrid GA, a coarse‐grain GA and a fine‐grain GA. The last two are based on models of natural evolution that are suitable for parallel implementation; they have been implemented on a hypercube and a Connection Machine. Experimental results show that the three GAs evolve good suboptimal solutions which are better than those produced by other methods. The GAs are also robust and do not show a bias towards particular problem configurations. The two parallel GAs have reasonable execution times, with the coarse‐grain GA producing better solutions for the allocation of loosely synchronous computations.
Dynamo ‐ a portable tool for dynamic load balancing on distributed memory multicomputers
Authors: Tarnvik Erik 
Published: November 2006

AbstractDynamic load balancing is an important technique when developing applications with unpredictable load distribution on distributed memory multicomputers. A tool, Dynamo, that can be used to utilize dynamic load balancing is presented. This tool separates the application from the load balancer and thus makes it possible to easily exchange the load balancer of a given application and experiment with different load balancing strategies. A prototype of Dynamo has been implemented in the C language on an Intel iPSC/2 Hypercube. Dynamo is demonstrated by two example programs. The first program solves the N queen problem using a backtracking algorithm and the second solves a 0‐1 knapsack problem using a depth‐first branch and bound algorithm.
A clock synchronization algorithm for the performance analysis of multicomputer systems
Authors: De Pietro Giuseppe , Villano Umberto 
Published: November 2006

AbstractThe paper deals with the implementation of global time in multicomputer systems. After a formalization of the synchronization problem, techniques to estimate the synchronization delay and to compensate the drift error are proposed. Then SYNC_WAVE, a clock synchronization algorithm where the values of a reference clock are diffused in a wave‐like manner, is described. SYNC_WAVE has no provision for fault‐tolerance and is specially designed to introduce low CPU and communication overhead, in order to support performance analysis applications efficiently. An implementation of the devised algorithm in a transputer‐based system is presented, showing the accuracy results obtained. Finally SYNC_WAVE is compared to other synchronization algorithms and several of its possible applications are suggested.
Experiences with networked parallel computing
Authors: Hoogerbrugge Peter , Mirchandaney Ravi 
Published: November 2006

AbstractThe performance and proliferation of workstations continues to increase at a rapid rate. However, the practical utilization of workstation networks for parallel computing is still in its infancy. This is due to the relative immaturity of programming tools, low bandwidth networks such as Ethernet, and high message latencies. However, programming tools are becoming more mature and network bandwidths are increasing rapidly. Hence, networks of commodity workstations may prove to be practical for certain classes of parallel applications.This paper describes our experiences with two applications parallelized on a network of Sun workstations. The first application is from Shell's petroleum engineering department. This program quantitatively derives rock and porefill composition from well‐log data, using a compute‐intensive iterative optimization procedure. The second application is time filtering, which is a fundamental operation performed on seismic traces.Through our experiments we identify the limits of networked parallel computing based on the current state of network technology. We also provide a discussion on the possible impact of future high speed networks on networked parallel computing.
Pipeline optimizations of the prime factor algorithm
Authors: Albrizio R. , Mazzone A. , Veneziani N. , Messina P. , Aloisio G. , Bochicchio M. 
Published: November 2006

AbstractThe prime factor algorithm (PFA) is an efficient discrete Fourier transform (DFT) computation algorithm used when the sequence length can be decomposed into mutually prime factors. Following our previous results on PFA decomposition carried out at Caltech on hypercube machines, we present in the paper a pipeline PFA implementation suitable for multiprocessor systems with distributed memory. This implementation achieves high values of efficiency and speed‐up when processing multiple sequences of data. The paper shows how an optimized structure can be obtained when the concurrency among computation and communications is exploited at each node of the pipe. Experimental results obtained on transputer‐based structures and on the IntelTouchstoneDelta system are also reported.
Evaluation of parallelization strategies for an incremental Delaunay triangulator in e3
Authors: Cignoni P. , Laforenza D. , Perego R. , Scopigno R. , Montani C. 
Published: November 2006

AbstractThe paper deals with the parallelization of Delaunay triangulation, a widely used space partitioning technique. Two parallel implementations of a three‐dimensional incremental construction algorithm are presented. The first is based on the decomposition of the spatial domain, while the second relies on the master‐slaves approach. Both parallelization strategies are evaluated, stressing practical issues rather than theoretical complexity. We report on the exploitation of two different parallel environments: a tightly coupled distributed memory MIMD architecture and a network of workstations co‐operating under the Linda environment Then, a third hybrid solution is proposed, specifically addressed to the exploitation of higher parallelism. It combines the other two solutions by grouping the processing nodes of the multicomputer into clusters and by exploiting parallelism at two different levels.
Computational similarity
Authors: Hockney Roger W. 
Published: November 2006

AbstractThe paper enunciates the principle of computational similarity, whereby calculations with the same values for certain dimensionless ratios are said to be ‘computationally similar’ and as a consequence have the same optimum self‐speed‐up and optimum number of processors. Based on a three‐parameter description of the computer hardware, two dimensionless ratios, which are only a function of the problem size and the hardware parameters, completely determine the scaling. Contours of constant self‐speed‐up can be drawn on a two‐dimensional dimensionless universal scaling diagram (DUSD). This diagram is for a particular class of timing expressions that can be shown to represent approximately the performance of a corresponding class of computer programs or benchmarks, but it applies to all computers describable by the three hardware parameters and to all problem sizes. Thus the dimensionless ratios play a similar role in the study of computer performance, as do the Reynolds and other dimensionless numbers in fluid dynamics. This dimensional analysis of computer performance is illustrated by the case of the FFT1 benchmark from the Southampton ‘Genesis’ distributed‐memory benchmarks.
PARADOX—a heterogeneous machine for the 3D vision algorithm
Authors: Wang Han , Brady Mike 
Published: November 2006

AbstractWe present in the paper a heterogeneous machine, PARADOX, designed in Oxford for real time image processing. PARADOX consists of a Datacube pipelined image processor, a configurable network of 32 T800 transputers, a Sun‐4 workstation and a special‐purpose interface connecting the Datacube to the transputer network. Its programming style is a mixture of MIMD paradigm employing a processor farm and interrupts to control the image processing pipeline in the Datacube via a VME bus. A number of vision algorithms including the Canny edge detector have been implemented on this machine at video rate. In particular, a 3D vision algorithm, Droid, has been implemented to provide navigation data for an autonomous guided vehicle.
Implementation of a fully balanced periodic tridiagonal solver on a parallel distributed memory architecture
Authors: Eidson T. M. , Erlebacher G. 
Published: November 2006

AbstractWhile parallel computers offer significant computational performance, it is generally necessary to evaluate several programming strategies. Two programming strategies for a fairly common problem—a periodic tridiagonal solver—are developed and evaluated. Simple model calculations as well as timing results are presented to evaluate these strategies.The particular tridiagonal solver evaluated is used in many computational fluid dynamic simulation codes. The feature that makes this algorithm unique is that these simulation codes usually require simultaneous solution for multiple right‐hand‐sides (RHS) of the system of equations. Each RHS solutions is independent and thus can be computed in parallel. Thus, a Gaussian‐elimination‐type algorithm can be used in a parallel computation and more complicated approaches such as cyclic reduction are not required.The two strategies are a transpose strategy and a distributed solver strategy. For the transpose strategy, the data are moved so that a subset of all the RHS problems is solved on each of the several processors. This usually requires significant data movement between processor memories across a network. The second strategy attempts to have the algorithm follow the data across processor boundaries in a chained manner. This usually requires significantly less data movement. An approach to accomplish this second strategy in a near‐perfect load‐balanced manner is developed. In addition, an algorithm will be shown to directly transform a sequential Gaussian‐elimination‐type algorithm into the parallel, chained, load‐balanced algorithm.
Partitioning of unstructured meshes for load balancing
Authors: Martin Olivier C. , Otto Steve W. 
Published: November 2006

AbstractMany large‐scale engineering and scientific calculations involve repeated updating of variables on an unstructured mesh. To do these types of computations on distributed memory parallel computers, it is necessary to partition the mesh among the processors so that the load balance is maximized and interprocessor communication time is minimized. This can be approximated by the problem of partitioning a graph so as to obtain a minimum cut, a well‐studied combinatorial optimization problem. Graph partitioning is NP complete, so for real world applications one resorts to heuristics, i.e. algorithms that give good but not necessarily optimum solutions. These algorithms include recursive spectral bisection, local search methods such as Kernighan‐Lin, and more general purpose methods such as simulated annealing. We show that a general procedure enables us to combine simulating annealing with Kernighan‐Lin. The resulting algorithm is both very fast and extremely effective.
Programming pipelined CAD applications on message‐passing architectures
Authors: Kenyon P. , Seth S. , Clematis A. , Agrawal P. , Dodero G. , Gianuzzi V. 
Published: November 2006

AbstractProgramming applications in computer‐aided design of VLSI are difficult on parallel architectures, especially pipelined implementations derived from their sequential counterparts by algorithmic partitioning. The difficulty is primarily due to lack of good program development environments and tools. Our solution, applicable to message‐passing architectures, is based upon a definition of a broad class of non‐linear pipeline configurations and an asynchronous data‐driven model for pipeline stage interactions. It provides object‐oriented definitions of stages and interconnecting channels. These objects are embedded in C++ so that the correctness of application programs can be tested on a workstation in a simulated environment. The simulation is instrumented to provide data useful in assessing relative computational loading and balancing of stages. Thus a large part of program development can take place in the environment of a workstation familiar to the programmer. A non‐trivial application is developed to illustrate these ideas.