bluuebunny/crossref_metadata_2025_split huggingface dataset:
Parallel rendering of volumetric data set on distributed‐memory architectures
Authors: Montani C. , Perego R. , Scopigno R. 
Published: November 2006

AbstractA solution is proposed to the problem of interactive visualization and rendering of volume data. Designed for parallel distributed memory MIMD architectures, the volume rendering system is based on the ray tracing (RT) visualization technique, the Sticks representation scheme (a data structure exploiting data coherence for the compression of classified data sets), the use of a slice‐partitioning technique for the distribution of the data between the processing nodes and the consequent ray‐data‐flow parallelizing strategy.The system has been implemented on two different architectures: an inmos Transputer network and a hypercube nCUBE 6400 architecture. The high number of processors of this latter machine has allowed us to exploit a second level of parallelism (parallelism on image space, or parallelism on pixels) in order to arrive at a higher degree of scalability. In both proposals, the similarities between the chosen data‐partitioning strategy, the communications pattern of the visualization processes and the topology of the physical system architecture represent the key points and provide improved software design and efficiency. Moreover, the partitioning strategy used and the network interconnection topology reduce the communications overhead and allow for an efficient implementation of a static load‐balancing technique based on the prerendering of a low resolution image.Details of the practical issues involved in the parallelization process of volumetric RT, commonly encountered problems (i.e. termination and deadlock prevention) and the sw migration process between different architectures are discussed.
Implementation of parallel algorithms for controlling robot manipulators
Authors: McKerrow P. J. , Fulcher J. A. 
Published: November 2006

AbstractWith the upsurge of interest in parallel processing during the 1980s, some researchers have applied such techniques indiscriminately, even in applications where little inherent concurrency exists. In the paper the kinematics of a 5‐DOF robot arm are investigated to assess the degree of parallelism contained within alternate robot models. This concurrency is mapped into occam processes, then control software generated to control the robot arm, firstly from a single transputer, then secondly from a network of transputers. On the basis of our findings, we conclude that there is limited parallelism which can be exploited in the Homogeneous transform model of the kinematics of a serial‐link manipulator. An alternative formulation of the kinematic model is required before much speed‐up can be achieved by parallel calculations. However, the architectures studied are suitable for modular manipulator systems, where joint transforms have to be calculated separately.
Model programs for computational science: A programming methodology for multicomputers
Authors: Hansen Per Brinch 
Published: November 2006

AbstractWe describe a programming methodology for computational science based on programming paradigms for multicomputers. Each paradigm is a class of algorithms that have the same control structure. For every paradigm, a general parallel program is developed. The general program is then used to derive two or more model programs, which solve specific problems in science and engineering. These programs have been tested on a Computing Surface and published with every detail open to scrutiny. We explain the steps involved in developing model programs and conclude that the study of programming paradigms provides an architectural vision of parallel scientific computing.
Parallel cellular automata: A model program for computational science
Authors: Hansen Per Brinch 
Published: November 2006

AbstractWe develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.
Competitive neural networks on message‐passing parallel computers
Authors: Ceccarelli Michele , Petrosino Alfredo , Vaccaro Roberto 
Published: November 2006

AbstractThe paper reports two techniques for parallelizing on a MIMD multicomputer a class of learning algorithms (competitive learning) for artificial neural networks widely used in pattern recognition and understanding. The first technique presented, following the divide et impera strategy, achieves O(n/p + logP) time for n neurons and P processors interconnected as a tree. A modification of the algorithm allows the application of a systolic technique with the processors interconnected as a ring; this technique has the advantage that the communication time does not depend on the number of processors. The two techniques are also compared on the basis of predicted and measured performance on a transputer‐based MIMD machine. As the number of processors grows the advantage of the systolic approach increases. On the contrary, the divide et impera approach is more advantageous in the retrieving phase.
Global communications on locally connected message‐passing parallel computers
Authors: Debbage Mark , Hill Mark B. , Nicole Denis A. 
Published: November 2006

AbstractModern multicomputer components such as the inmos T800 and the Texas Instruments TMS320C40 provide hardware which supports efficient communication between directly connected processors. The paper describes techniques which have been developed to provide efficientglobalcommunications for machines based on these and similar processors. This service is implemented by a packet‐routing kernel adopting a standard, portable communications interface. The design of this kernel is discussed with particular emphasis on the manner in which it guarantees reliable, lightweight, deadlock‐free communication for arbitrary interconnection topologies. The kernel has been developed and tested on transputers. Extensive results on the performance of the router are presented to demonstrate that the substantial advantages associated with its well founded, structured design are not at odds with high efficiency. This router has been used to support several multi‐transputer environments, including a commercially available POSIX‐conformant operating system and a distributed occam environment freed from conventional configuration constraints.
Tmon: A performance monitor for transputer‐based multicomputers
Authors: Wagner A. , Jiang J. , Chanson S. 
Published: November 2006

AbstractThe paper describes a new performance monitoring tool, calledTmon, that has been developed to help application programmers understand the run‐time behavior of a parallel system and tune the performance of their programs. Tmon measures resource utilization and traces process activities transparently during execution. A global interrupt technique used by Tmon allows measurement tasks to be executed simultaneously on different processors and an accurate global clock to be maintained with minimal overhead. Experimental results indicate that both the accuracy and the overhead of the monitor are well within an acceptable range. We introduce a performance model from which it is possible to derive several different parallel programming metrics. A weighted critical path analysis tool is also presented that focusses the user's attention on those parts of the program whose modification would most improve performance. An example in which the tool is used successfully to improve the performance of a parallel application is also presented. Tmon is currently implemented on top of the Trollius Operating System and runs on a 74‐node transputer‐based multicomputer.
Monitoring and visualizing multiprocessor interconnection network contention
Authors: Zhang Hiaodong , Wang Beichang 
Published: November 2006

AbstractMultistage Interconnection Networks (MIN) have been widely used for building large‐scale shared‐memory multiprocessor systems. Complex interactions between many processors and memory modules through the MIN, (such as interprocessor communication, process scheduling and synchronization and remote‐memory access) result in a significantly large space of possible performance behavior and potential performance bottlenecks. To provide insight into dynamic system performance, we have developed an integrated data collection, analysis, and visualization environment for a MIN‐based multiprocessor system, called MIN‐Graph. The MIN‐Graph is a graphical instrumentation monitor to aid users in investigating performance problems and in determining an effective way to exploit the high performance capabilities of interconnection network multiprocessor systems. Interconnection network contention is a major bottleneck of parallel computing on MIN‐based multiprocessors. This paper focuses on evaluating the contention behavior through performance monitoring and visualization. Four sets of system and scientific application programs with different programming and scheduling models and different memory access patterns are monitored and tested to observe the various network contention behaviors. The MIN‐Graph is implemented on the BBN GP1000 and the BBN TC2000.
Parallel simulation based on conservative time windows: A performance study
Authors: Ayani Rassul. , Rajaei Hassan 
Published: November 2006

AbstractThe paper presents a Conservative Time Window (CTW) algorithm for parallel simulation of discrete event systems. The physical system to be simulated is partitioned intondisjoint sub‐systems, each of which is represented by an object The CTW algorithm identifies a time window for each object, such that events occurring in each window are independent of events in other windows and thus they can be processed concurrently. The CTW algorithm was implemented on a shared memory multiprocessor, a Sequent Symmetry S81 with 16 processors. We measured performance of the CTW algorithm on two types of network topologies: feed‐forward networks and networks with feedback loops. We used three metrics to measure performance: speed‐up, average number of independent windows detected by the algorithm, and average number of events occurring in each window. We also investigated the impact of various event scheduling policies on performance. The results obtained show that the CTW algorithm produces good performance in many cases.
Performance modeling of load‐balancing algorithms using neural networks
Authors: Ahmad Ishfaq , Mehrotra Kishan , Mohan Chilukuri K. , Ranka Sanjay , Ghafoor Arif 
Published: November 2006

AbstractThe paper presents a new approach that uses neural networks to predict the performance of a number of dynamic decentralized load‐balancing strategies. A distributed multicomputer system using distributed load‐balancing strategies is represented by a unified analytical queuing model. A large simulation data set is used to train a neural network using the back‐propagation learning algorithm based on gradient descent The performance model using the predicted data from the neural network produces the average response time of various load balancing algorithms under various system parameters. The validation and comparison with simulation data show that the neural network is very effective in predicting the performance of dynamic load‐balancing algorithms. Our work leads to interesting techniques for designing load balancing schemes (for large distributed systems) that are computationally very expensive to simulate. One of the important findings is that performance is affected least by the number of nodes, and most by the number of links at each node in a large distributed system.
Time‐parallel solution of linear partial differential equations on the Intel Touchstone Delta supercomputer
Authors: Toomarian Nikzad , Fijany Amir , Barmen Jacob 
Published: November 2006

AbstractThe paper presents the implementation of a new class of massively parallel algorithms for solving certain time‐dependent partial differential equations (PDEs) on massively parallel supercomputers. Such PDEs are usually solved numerically, by discretization in time and space, and by applying a time‐stepping procedure to data and algorithms potentially parallelized in the spatial domain. In a radical departure from such a strictly sequential temporal paradigm, we have developed a concept of time‐parallel algorithms, which allows the marching in time to be fully parallelized. This is achieved by using a set of transformations based on eigenvalue‐eigenvector decomposition of the matrices involved in the discrete formalism. Our time‐parallel algorithms possess a highly decoupled structure, and can therefore be efficiently implemented on emerging, massively parallel, high‐performance supercomputers, with a minimum of communication and synchronization overhead. We have successfully carried out a proof‐of‐concept demonstration of the basic ideas using a two‐dimensional heat equation example implemented on the Intel Touchstone Delta supercomputer. Our results indicate that linear, and even superlinear, speed‐up can be achieved and maintained for a very large number of processor nodes.
Dynamic load‐balancing for PDE solvers on adaptive unstructured meshes
Authors: Walshaw Chris , Berzins Martin 
Published: November 2006

AbstractModern PDE solvers written for time‐dependent problems increasingly employ adaptive unstructured meshes (Flaherty et al., 1989) in order to both increase efficiency and control the numerical error. If a distributed memory parallel computer is to be used, there arises the significant problem of dividing the domain equally amongst the processors whilst minimising the inter‐subdomain dependencies. A number of graph‐based algorithms have recently been proposed for steady‐state calculations. The paper considers an extension to such methods which renders them more suitable for time‐dependent problems in which the mesh may be changed frequently.
SCIDDLE: A tool for large scale distributed computing
Authors: Arbenz Peter , Sprenger Christoph , Luthi Hans Peter , Vogel Stefan 
Published: November 2006

AbstractWe report on a portable communication environment, ‘SCIDDLE’, for distributing computations over heterogenous networks of UNIX computers. SCIDDLE is based on the client‐server model. It was designed to support the distribution of large scale numerical computations and to keep its usage as simple as possible. All interprocess communication is done via remote procedure calls. The user defines the interface between communicating processes in a simple declarative language. Parallel programming is supported by asynchronous RPCs. A convenient array handing has been implemented. We demonstrate the usefulness of the system with an application from quantum chemistry on internet‐connected workstations and supercomputers.
Comparative study of task duplication static scheduling versus clustering and non‐clustering techniques
Authors: Shirazi Behrooz , Chen Hsing‐Bung , Marquis Jeff 
Published: November 2006

AbstractOne of the major issues that needs to be addressed in distributed memory multiprocessor (DMM) systems is the program task partitioning and scheduling problems, i.e. mapping of an application program's precedence related task threads among the processing elements of a DMM system. The optimal task partitioning and scheduling problem, with the goal of minimizing the program execution time and interprocessor communication overhead, is known to be an NP‐complete problem. The paper addresses the design, development and performance evaluation of a novel static task partitioning and scheduling method called linear clustering with task duplication (LCTD). LCTD employs the linear (sequential) execution of tasks and task duplication heuristics in achieving minimized computation and interprocessor communication delays in DMMs. The superiority of the proposed LCTD algorithm is demonstrated through simulation studies and comparison against several of the existing static scheduling schemes, such as heavy node first (HNF) and linear clustering. We show that the proposed method can obtain an average of 33% improvement in program execution time and 21% improvement in processor utilization compared to linear clustering and HNF methods.
A fast recursive mapping algorithm
Authors: Chen Song , Eshaghian Mary M. 
Published: November 2006

AbstractThe paper presents a generic technique for mapping parallel algorithms onto parallel architectures. The proposed technique is a fast recursive mapping algorithm which is a component of the Cluster‐M programming tool. The other components of Cluster‐M are the Specification module and the Representation module. In the Specification module, for a given task specified by a high‐level machine‐independent program, a clustered task graph called Spec graph is generated. In the Representation module, for a given architecture or computing organization, a clustered system graph called Rep graph is generated. Given a task (or system) graph, a Spec (or Rep) graph can be generated using one of the clustering algorithms presented in the paper. The clustering is done only once for a given task graph (system graph) independent of any system graphs (task graphs). It is a machine‐independent (application‐independent) clustering, and therefore it is not repeated for different mappings. The Cluster‐M mapping algorithm presented produces a sub‐optimal matching of a given Spec graph containing M task modules, onto a Rep graph of N processors, in O(MN) time. This generic algorithm is suitable for both the allocation problem and the scheduling problem. Its performance is compared to other leading techniques. We show that Cluster‐M produces better or similar results in significantly less time and using fewer or an equal number of processors as compared to the other known methods.
Task assignment using a problem‐space genetic algorithm
Authors: Ahmad Imtiaz , Dhodhi Muhammad K. 
Published: November 2006

AbstractThe task assignment problem is one of assigning tasks of a parallel program among the processors of a distributed computing system in order to reduce the job turnaround time and to increase the throughput of the system. Since the task assignment problem is known to be NP‐complete except in a few special situations, satisfactory suboptimal solutions obtainable in a reasonable amount of computation time are generally sought. In the paper we introduce a technique based on the problem‐space genetic algorithm (PSGA) for the static task assignment problem in both homogeneous and heterogeneous distributed computing systems to reduce the task turnaround time and to increase the throughput of the system by properly balancing the load and reducing the interprocessor communication time among processors. The PSGA based approach combines the power of genetic algorithms, a global search method, with a simple and fast problem‐specific heuristic to search a large solution space efficiently and effectively to find the best possible solution in an acceptable CPU time. Experimental results on test examples from the literature show considerable improvements in both the assignment cost and the CPU times over the previous work. The proposed scheme is also applied to a digital signal processing (DSP) system consisting of 119 tasks to illustrate its balancing properties and computational advantage on a large system. The proposed scheme offers 12–30% improvement in the assignment cost as compared to the previous best known results for the DSP example.
A partitioning advisory system for networked data‐parallel processing
Authors: Crandall Phyllis E. , Quinn Michael J. 
Published: November 2006

AbstractWith the increased performance capabilities of desktop computers, networked computing has become a popular vehicle for using parallelism to solve a variety of computationally intense problems. However, node heterogeneity and high communication costs may limit performance unless the problem space is carefully partitioned across the network in a way that considers both the capabilities of the machines and the high network communication costs. We describe an advisory system that is designed to help the programmer, compiler or run‐time environment choose the best decomposition strategy for partitioning specific data‐parallel applications across a given collection of machines. The system includes provisions for assessing the capabilities of the participating machines and the network in light of the current workload. Given information about the problem space, the machine speeds and the network, the system provides a ranking of three standard partitioning methods. We test the validity of our system by comparing the observed relative performance with predicted relative performance of different data decompositions on a program with a variable number of floating point operations and a 5‐point stencil communication pattern.
Beyond software performance visualization
Authors: Abrams M. , Lee T. J. , Cadiz H. T. , Ganugapati K. 
Published: November 2006

AbstractPerformance visualization tools of the past decade have yielded new insights into the behavior of sequential, parallel and distributed programs. However, they have three inherent limitations: (1) they only display what happened in one execution of a program (this is dangerous when analyzing concurrent applications, which are prone to non‐deterministic behavior); (2) a human uses one or more bandwidth‐limited senses with a visualization tool (this limits the scalability of a visualization tool); (3) the relationship of ‘interesting’ program events is often separated in time by other events; thus discerning time‐dependent behavior often hinges on finding the ‘right’ visualization—a possibly time‐consuming activity. CHITRA93 complements visualization systems, while alleviating these limitations, and analyzes a set (or ensemble) of traces by combining the visualization of a few traces with a statistical analysis of the entire ensemble (overcoming (1)). It reduces the ensemble to empirical models that capture the time‐dependent relationships of ‘interesting’ program events through application, programming language and computer architecture independent analysis techniques (addressing (2) and (3)). It also incorporates the following transforms, such as aggregation, that simplify the ensemble and reduce the state‐space size of the models generated; a user interface that allows certain transforms to be selected by editing the visualization with a mouse; homogeneity tests that allow partitioning of an ensemble; an efficient semi‐Markov model generation algorithm whose computation time is linear in the sum of the lengths of the traces comprising the ensemble; and a CHAID‐based model that can fathom non‐Markovian relationships among transitions in the traces. The use of CHITRA93 is demonstrated by partitioning ten parallel database traces with nearly 8,000 states into two homogeneous subsets, each modeled by an irreducible, periodic and hierarchical stochastic process with as few as four states.