Session
01-A.1
Topic 01: Support Tools and Environments
Online visualization and computational steering is an active research issue since quite a few years. The use of high performance scientific applications in heterogeneous computing environments still reveals many problems. With OViD we address problems that arise from distributed applications with no global data access and present additional collaboration features for distributed teams working with one simulation. OViD provides an interface for parallel and distributed scientific applications to send their distributed data to OViD's object pool. Another interface allows multiple visualization systems to attach to a running simulation, access the collected data from the pool, and send steering data back.
In this paper, we present a web-based unstructured mesh partitioner and load balancer (UMPAL). UMPAL is an integrated tool that consists of five components, a partitioner, a load balancer, a simulator, a visualization tool, and a Web interface.
Software tools have nowadays become indispensable for program development, yet the desire to combine them to provide enhanced functionality has still to be realised. Existing tool environments integrate a number of tools, but do not achieve interoperability and lack extensibility. Integration of new tools can typically necessitate the redesign of the whole system. We describe a new framework for an open tool environment, which facilitates tool development, permits easy tool integration, and allows interoperability. Results consist of a reference model for the system's architecture, a categorisation of supported tools and several interoperability scenarios which need further evaluation.
In an era dominated by the rapid development of faster and cheaper processors it is difficult both for the application developer and system architect to make intelligent decisions about application interaction with system memory hierarchy. We present ToolBlocks, an object oriented system for the rapid development of memory hierarchy models and analysis. With this system, a user may build cache and prefetching models and insert complex analysis and visualization tools to monitor their performance. A set of commonly used cache and analysis tools are already available, and the system is completely and easily extendible and sharable.
Session
01-A.2
Automatic parallelisation tools implement sophisticated tactics for analysing and transforming application codes but, typically, their ``one-step'' strategy for finding a ``good'' parallel implementation remains naive. In contrast, successful experts at parallelisation attempt to explore the space of possible implementations. Finesse is an environment which supports this exploration by automating many of the tedious steps associated with experiment planning and execution and with the analysis of performance. Finesse also harnesses the sophisticated techniques provided by automatic compilation tools to provide feedback to the user which can be used to guide the exploration. This paper briefly describes Finesse and presents evidence for its effectiveness. The latter has been gathered from the experiences of a small number of users, both expert and non-expert, during their parallelisation efforts on a set of compute-intensive, kernel test codes. The evidence lends support to the hypothesis that users of Finesse can find implementations that achieve performance comparable with that achieved by expert programmers, but in a much shorter time.
Automatic differentiation is a powerful technique for the evaluation of derivatives of functions defined by computer programs. Here, a program is treated as a sequence of elementary statements to which the chain rule is applied over and over again. Combining automatic differentiation and the organizational structure of toolkits for parallel scientific computing provides a mechanism to exploit mathematical insight on a higher level. Algorithmic structures such as BLAS-like operations, linear and nonlinear solvers, or integrators for ordinary differential equations can be identified by their standardized interfaces and recognized as high-level mathematical objects rather than as a sequence of elementary statements.
Object-oriented programming, design patterns, and frameworks are abstraction techniques that have been used to reduce the complexity of sequential programming. The CO2P3S parallel programming system provides a layered development process that applies these three techniques to the more difficult domain of parallel programming. The system generates correct frameworks from pattern template specifications at the highest layer and provides performance tuning opportunities at lower layers. Each of these features is a solution to a major problem with current parallel programming systems. This paper describes CO2P3S and its highest level of abstraction using an example program to demonstrate the programming model and one of the supported pattern templates. Our results show that the system can be used to quickly generate a correct parallel structure that can be the basis of a parallel program with good performance improvements.
Session
19-A.1
As we research to make the use of Computational Grids seamless, the allocation of resources in these dynamic environments is proving to be very unwieldy. In this paper, we introduce, describe and evaluate a technique we call request sequencing. Request sequencing groups together requests for Grid services to exploit some common characteristics of these requests and minimize network traffic. The purpose of this work is to develop and validate this approach. We show how request sequencing can affect scheduling policies and enable more expedient resource allocation methods.
The emerging infrastructures supporting transparent use of heterogeneous distributed resources enable the design of a new class of applications. These meta-applications are composed of distributed software components. In this paper we describe a new model for component based meta-application design based on a formal architectural description of the gross organization of an application. This structural description is enriched by a formal process algebraic characterization of component behavior. Using this behavioral model we can formally check meta-applications in an early development phase. We present simple architectural styles developed to support data-flow and control-flow driven meta-application design on top of the Amica metacomputing infrastructure.
Session
19-A.2
Javelin is a Java-based infrastructure for parallel Internet computing. This paper presents Javelin 2.0, focusing on the enhancements that distinguish it from prior versions of Javelin. With regard to architecture, the paper presents enhancements that facilitate aggregating larger sets of host processors. The paper then presents: a branch-and-bound computational model, the supporting Javelin 2.0 architecture, a scalable task scheduler using distributed work-stealing, a distributed eager scheduler, implementing fault tolerance, and the results of performance experiments. Taken as a whole, Javelin 2.0 frees application developers from concerns about complex interprocessor communication and fault tolerance among Internetworked hosts. When all or part of their application can be cast as a piecework or a branch-and-bound computation, Javelin 2.0 allows developers to focus on the underlying application without sacrificing performance.
The design of application for Computational Grids relies partly on communication paradigms. In most of the Grid experiments, message-passing has been the main paradigm either to let several processes from a single parallel application to exchange data or to allow several applications to communicate between each others. In this article, we advocate the use of a modern approach for programming a Grid. It is based on the use of distributed objects, namely parallel CORBA objects. We focus our attention on the handling of distributed data within parallel CORBA objects. We show some performance results that were obtained using a NEC Cenju-4 parallel machine connected to a PC cluster.
t.b.d. (click here for some more information)
Session
03-A.1
Irregular problems require the computation of some properties for a set of elements irregularly distributed in a domain. The distribution may change during the computation in a way that cannot be foreseen in advance. Most irregular problems satisfy a locality property because the properties of an element e depend on the elements "close" to e. We propose a methodology to develop a highly parallel solution based upon a load balancing strategy that respects locality. We also discuss the update of the mapping at run time together with strategies to acquire data on elements mapped onto other processing nodes.
Hardware performance counters in microprocessors can now generate profile data cheaply. Translating aggregate data such as basic block execution frequencies from the executable to the compiler intermediate representation is fairly straight-forward. In this paper, we show how to use Compaq's DCPI tool to determine load latencies which are at a fine, instruction granularity and then use them to provide fodder for improving instruction scheduling. We validate our use of DCPI latency data to classify approximately 75% of loads as hits or misses against simulation numbers, demonstrating that we can gather correct fine grain latencies cheaply at run time. We map our classification into the Multiflow compiler's intermediate representation, and use a locality sensitive Balanced scheduling algorithm. Our experiments illustrate that our algorithm has the potential to improve run times when compared to Balanced scheduling, but that a variety of pitfalls make consistent improvements difficult to attain.
We describe a static load balancing algorithm based on Kohonen Self-Organizing Maps (SOM) for a class of parallel computations where the communication pattern exhibits spatial locality and we present initial results. The topology preserving mapping achieved by SOM is used to reduce the communication and a load balancing mechanism is introduced into the SOM algorithm. We also present a preliminary multilevel implementation which resulted in significant improvements. The results are promising to further improve SOM based load balancing for geometric graphs.
Session
03-A.2
This paper evaluates the impact of task migration on gang-scheduling of parallel jobs for distributed systems. With migration, it is possible to move tasks of a job from their originally assigned set of nodes to another set of nodes, during execution of the job. This additional flexibility creates more opportunities for filling holes in the scheduling matrix. We conduct a simulation-based study of the effect of migration on average job slowdown and wait times for a large distributed system under a variety of loads. We find that migration can significantly improve these performance metrics over an important range of operating points. We also analyze the effect of the cost of migrating tasks on overall system performance.
Time-sliced gang scheduling improves the average response time of the jobs in a typical job stream. Recent research has shown that time-slicing is most effective when the jobs admitted for execution fit entirely into physical memory. We investigate two techniques for improving the performance of gang scheduling in the presence of memory pressure: 1) a novel backfill approach which improves memory utilization, and 2) an adaptive multi-programming level which balances processor/memory utilization with job response time performance. Our simulations show that these techniques reduce theslow-down performance metrics over naive FCFS methods on a distributed memory parallel system.
In the static mapping approach a parallel program is modelled as a task graph characterizing its structure. The models currently in use are the Task Precedence Graph and the Task Interaction Graph. In this paper we use a new model, the Temporal Task Interaction Graph (TTIG), which is automatically generated with a specific tool. The TTIG combines these two previous models by explicitly capturing the temporal behaviour of program tasks. Experimentation was performed in a current PVM environment, for a set of synthetic graphs which exhibit different ratios of computation/communication cost. The execution times when these programs are mapped using the PVM default scheme or using the information contained in the TTIG where compared. The results confirm that with the TTIG model better assignments are obtained, providing improvements of up to 49% compared with the PVM assignments.
Session
07-A.1
We propose a 3D reconstruction algorithm based upon Fourier analysis using Cartesian coordinates. We discuss the accuracy of the algorithm and present comparisons of values computed by a parallel program implementing the algorithm with known solutions. Our results are consistent with the ones produced by a sequential program used for many years for structural biology studies. We report the speedup and the load balancing results for processing cryo-EM data for several viruses. We use a cluster of inexpensive PCs interconnected by a switched Ethernet to carry out the 3D reconstruction. The algorithm is general and can be used for 3D reconstruction of asymmetric objects for applications other than structural biology.
The computational requirements of cloth and other non-rigid solid simulations are high and often the running time is far from real time. In this paper, an efficient solution of the problem on parallel computer is presented. An application, which combines data parallelism with task parallelism has been developed, achieving a good load balancing and minimizing the communication cost. The execution time obtained for a typical problem size, its superlinear speed-up, and the isoscalability shown by the model, will allow to reach real-time simulations in sceneries of growing complexity, using the most powerful multiprocessors.
Geographical Information Systems (GIS) manipulate spatial data. The vector-topological data format retains the topological relationships between geographical features and is commonly used in a range of geographical data analyses. There are a number of characteristics of the format, however, that cause difficulties in the input, manipulation and processing of the data. This paper reports on the performance of a prototype parallel data partitioning algorithm for the input of vector-topological data to parallel processes.
In this paper we propose a parallel technique of the training phase for automatic speech recognition using the Hidden Markov Models (HMM) which improves the load balancing in the previous proposed parallel implementations. This technique is based on an efficient distribution of sentences of the vocabulary on processors taking into account not only the size of the vocabulary but also the length of each sentence. In this manner the idle time will be reduced. The experimental results show that good performances can be obtained with this distribution
Session
07-A.2
Parallelization of non-trivial scientific applications remains a nontrivial task typically requiring some programmer assistance. Key considerations for candidate parallel programming paradigms are portability, and intuitive use, at times mutually exclusive features. In this study two similar parallelization tools, Pfortran and Cray's Co-Array Fortran, are discussed in the parallelization of Quantum Dynamics, a non-trivial scientific application.
The simulated models and requirements of engineering programs like computational fluids dynamics and structural mechanics grow more rapidly than single processor performance. Automatic parallelisation seem to be the obvious approach for huge and historic packages like PERMAS. The approach is based on dynamic scheduling, which is more flexible than domain decomposition, is totally transparent to the end-user and shows good speedups because it is able to extract parallelism where others are not. In this paper we show the need of some preparatory steps on the big input matrices for good performance. We present a new approach for blocking that saves storage and decreases the computation critical path. Also a data distribution step is proposed that drives the dynamic scheduler decisions such that an efficient parallelisation can be achieved even on slow multiprocessor networks. A final and important step is the interleaving of the array blocks that are distributed to different processors. This step is essential to expose the parallelism to the scheduler.
An implementation of a real symmetric eigensolver on parallel processors is described and evaluated. To achieve better performance in the inverse iteration part, a multi-color framework is introduced, in which the order of the orthogonalizations are rescheduled so that the inverse iterations are executed concurrently. With the blocked tridiagonalization and backtransformation, our real symmetric eigensolver shows good performance and accuracy both on the MPP SR2201 and on the newly developed hybrid machine SR8000.
The purpose of this paper is to investigate the efficient parallelization of Fast Hartley Transforn (FHT) algorithm on shared memory multiprocessor systems. The computational dependencies of the sequential FHT algorithm are analyzed, in order to distribute the loops of the algorithm among multiple threads, executed on the available processors of the system. The outer loop of the algorithm carries data dependencies between consecutive iterations and, for parallel execution, synchronization barriers are required. The performances of the parallel FHT algorithm are estimated; the results show a significant speed-up in the parallel execution of the FHT algorithm.
This paper compares the functional programming language SAC to other data parallel languages, in particular Fortran-90/HPF, with respect to specificational elegance and runtime performance. A well-known benchmark, red/black successive over-relaxation, serves as a case study. After presenting the HPF reference implementation and an initial SAC solution, alternative SAC implementations are discussed that demonstrate the expressive power of the language. Comprehensive performance figures eventually show the ability to compile these highly generic SAC specifications into machine code that clearly outperforms the HPF implementation on a shared memory multiprocessor.
This paper reports a study of mapping sparse matrix computation, sparse Matrix Vector Multiplication (MVM), on a parallel computing platform based on a fine-grained multithreaded program execution model. Such sparse MVM computation, when parallelized without performing graph partitioning, offers a very high communication to computation ratio, and is well known to have a very limited scalability on traditional distributed memory machines. The particular multithreaded system we use is the EARTH model, which can be implemented from off-the-shelf processors without extensive special hardware support. With the NAS class B input sparse matrix (with 75,000 rows), we observed an absolute speedup of 90 on 120 nodes of a distributed memory configuration. This is achieved without using {\em inspector/executor} or {\em graph partitioning}, or any communication minimization phase, which means that same performance can be achieved on adaptive problems as well. High scalability is achieved because of a number of charactestics of the EARTH architecture: asynchronous execution, low communication overheads, ability to overlap communication and computation and low context-switching costs.
Networks Of Workstations (NOWs) are a cheaper alternative to achieving high performace over expensive, parallel platforms. The BSP model provides a simple and portable programming discipline that is particularly suitable for coarse-grained parallel systems such as NOWs. We examine the issue of predictivity of the BSP cost model for a NOW consisting of SUN workstations connected through a 10Mbps Ethernet network. In particular, we compare the original BSP cost function with a number of new variants, with the intent of improving predictivity by having the cost function encompass parameters of the hardware/software system which have the largest impact on performance.
OpenMP offers a high-level interface for parallel programming on scalable shared memory (SMP) architectures providing the user with simple work-sharing directives while relying on the compiler to generate parallel programs based on thread parallelism. However, the lack of language features for exploiting data locality often results in poor performance since the non-uniform memory access times on scalable SMP machines cannot be neglected. HPF, the de-facto standard for data parallel programming, offers a rich set of data distribution directives in order to exploit data locality, but has mainly been targeted towards distributed memory machines. In this paper we describe an optimized execution model for HPF programs on SMP machines that avails itself with the mechanisms provided by OpenMP for work sharing and thread parallelism while exploiting data locality based on user-specified distribution directives. This execution model has been implemented in the ADAPTOR HPF compilation system and experimental results verify the efficiency of the chosen approach.
Session
10-A.2: Structured Parallel Programming
The paper describes the Skel-BSP Global Optimizer, a compile-time technique tuning the structure of skeletal programs according to the characteristics of the target architecture. The GO uses a set of optimization rules predicting the costs of each skeleton. The optimization rules refer to a set of implementation templates developed on top of the EdD-BSP (a variant of the BSP model). The paper describes the Program Annotated Tree representation and the set of transformation rules utilized by the GO to modify the starting program. The optimization phases: balancing, scaling and augmenting are presented and explained running the GO on a cluster of PCs for an image analysis toy-program
We developed a theory in order to address crucial questions of program design methodology. We think that it could unify two concepts of data parallel programming that we consider fundamental as they concern data locality expression: the notions of alignment in HPF and shape in C*. In this article, we aim at measuring the efficiency of programs, and the impact of program transformations on efficiency. For this, we give a formal operational semantics to the statements in the aforementioned theory.
A design pattern is a description of a high-quality solution to a frequently occurring problem in some domain. A pattern language is a collection of design patterns that are carefully organized to embody a design methodology. A designer is led through the pattern language, at each step choosing an appropriate pattern, until the final design is obtained in terms of a web of patterns. This paper describes a pattern language for parallel application programs. The goal of our pattern language is to lower the barrier to parallel programming by guiding a programmer through the entire process of developing a parallel program. The main target audience is experienced programmers who may lack experience with parallel programming. The programmer brings to the process a good understanding of the actual problem to be solved, then works through the pattern language to obtain a detailed parallel design or perhaps working code.
A Bulk Synchronous Parallel (BSP) computation consists of a sequence of supersteps, separated by barrier synchronizations. Several authors recognize that a barrier synchronization is expensive in current parallel architectures and propose to expand the BSP software with a zero cost synchronization mechanism, which can be used when the number of messages due to receive is known. This mechanism is usually known as "oblivious synchronization". The use of oblivious synchronizations implies that, opposite to what occurs in the original BSP model, different processors can be in different supersteps at a given time. However, the BSP semantic can be preserved by the underlying BSP software by numbering the supersteps and controlling that, when a message with an invalid number arrives, the receive thread puts it in a queue, where it waits until the correct superstep is reached. An unwanted consequence of these software improvements is a loss of accuracy when using the BSP complexity model to predict the running time. This paper proposes an extension of the BSP complexity model to deal with oblivious barriers and shows its accuracy for a case example.
We introduce a component software architecture designed for demanding grid computing environments that allows the optimal performance of the assembled component applications to be achieved. Performance over the assembled component application is maintained through inter-component static and dynamic optimisation techniques. Having defined an application through both its component task and data flow graphs we are able to use the associated performance models to support application level scheduling. By building grid aware applications through reusable interchangeable software components with integrated performance models we enable the automatic and optimal partitioning of an application across distributed computational resources.
This paper examines the behavior of current and next generation microprocessors' fetch engines and which parameters of its design are key to overall performance while running DSS workloads. Main fetch engine design decisions are re-evaluated in the context of DSS workloads, and several tradeoffs between them are discussed. In particular, we analyze the effect of the three major aspects that characterize fetch performance, the latency of instructions being fetched, their quality and the number of instructions that the fetch engine provides per access. The second part of our study focuses on the performance benefits of the Software Trace Cache (STC) as a code reordering technique for our DSS workload.
A typical BTB requires a few kbyte of storage which makes it rather large and, because it is accessed every cycle, rather power consuming. Partial resolution has in the past been proposed to reduce the size of a BTB. A partial resolution BTB stores not all tag bits that would be required to do an exact lookup. The result is a smaller BTB at the price of slightly less accurate branch prediction. This paper proposes to make use of branch locality to reduce the size of a BTB. Short-distance branches need fewer BTB bits than long-distance branches that are less frequent.
The amount of information recorded in the prediction tables of the proposed address predictors turns out to be comparable to the current on-chip cache sizes; for instance, a last-address predictor that records 4.096 64-bit effective addresses uses a 32 Kbytes storage space. Area cost of address predictors is proportional to address width. To reduce their area cost, we will take advantage of the spatial-locality property of the memory references, that is, the high-order bits of several effective addresses recorded in the prediction table are equal. Then, the effective addresses are split in two parts: the high-order bits and the low-order bits. The High-Address Table records the high-order bits and the Low-Address Table records the low-order bits and a link between tables. This organization allows addresses with the same high-order bits to share one entry in the High-Address Table. We use this organization in a last-address predictor and our evaluations show that it produces significant area-cost reductions (28%-60%) without performance losses.
We are proposing a cache addressing scheme based on hashing intended to decrease the miss ratio of small size caches. The main intention is to improve the hit ratio for 'random' patterns pointer memory accesses for embedded (special purpose) system applications. We introduce a hashing scheme, denoted as bit juggling, and measure the effect such a scheme has in the cache access miss ratio. It is shown, for the considered benchmark, that 3-bit bit juggling will reduce the miss ratio for up to 12\%, for associative caches of maximum size of 8KBytes when compared to usual cache addressing schemes.
Many important applications perform computations on values of non-standard bit-width; mapping them to word-based processing units is wasteful of resources and results in suboptimal performance. While there are processor architectures which take advantage of varying bit-widths, compiler optimizations lag far behind. We present BitValue, a compiler algorithm which infers reduced widths and discovers constant bits. BitValue performs a forward analysis, which finds constant bits and bits independent of the inputs and a backward analysis, which discovers bits unused by the output. BitValue inference can determine that on average 25% of the bit computations are unnecessary for programs from MediaBench and SPEC95.
Generalised matrix-matrix multiplication forms the kernel of many mathematical algorithms. A faster matrix-matrix multiply immediately benefits these algorithms. In this paper we implement efficient matrix multiplication for large matrices using the floating point Intel Pentium SIMD architecture. A description of the issues and our solution is presented, paying attention to all levels of the memory hierarchy. Our results demonstrate an average performance of 1.8 times faster than the leading public domain matrix-matrix multiply routines and comparable performance with Intel's SIMD small matrix-matrix multiply routines.
In general, redundant arithmetic speeds up truly dependent arithmetic computations by eliminating unnecessary conversions between intermediate and two's complement forms. Also, it enables a shorter clock cycle by reducing addition latency. Intermediate values during computations are expressed in redundant number representations that use multiple bits to indicate the value of a single digit. By exploiting the dependency of selected operations, significant speedup can be obtained by removing excess sub-operations (conversions). This approach has been extensively explored in the field of DSP and floating-point operations. The carry-free characteristic of redundant arithmetic provides a scalable solution for addition of increased data path width for 64 bit processors. Optimal scheduling for redundant arithmetic requires operand redundancy, opcode, and dependency information. We present the novel concept of the extended carry-save optimization to improve the performance of redundant processing. We also examine the effectiveness of redundant processing by exploring the issue of instruction scheduling. Finally, the framework and methodologies currently used for analysis will be described. Initial data on the potential speedup will be presented while more details are currently being gathered for further analysis.
Data prefetching is an attractive way to limit the impact of memory latency by reducing the frequency of cache misses. Decoupled processing seeks to dynamically schedule memory accesses in order to tolerate memory latency by prefetching operands. Since decoupled processors can not speculatively issue memory operations, control flow operations can significantly impact their ability to prefetch data. The prefetching architecture proposed here seeks to leverage the dynamic scheduling benefits of decoupled processing while allowing memory operations to be speculatively invoked. Evaluations using the SPEC95 benchmarks resulting in speed-ups of over 40% of peak for most of the inputs.
Instruction-level parallelism of stack codes like Java is severely limited by accessing the operand stack sequentially. To resolve this problem, our earlier works have presented stack operations folding to reduce the number of push/pop operations in between the operand stack and the local variable. In those studies, Java bytecodes are classified into three major POC types. Statistical data indicates that the 4-foldable strategy of the POC folding model can eliminate 86% of push/pop operations. In this paper, we propose an Enhanced POC (EPOC) folding model to eliminate more than 99% of push/pop operations with an instruction buffer size of 8 bytes and the same 4-foldable strategy. The average issued instructions per cycle for a single pipelined architecture is further enhanced from 1.70 to 1.87.
Session
02-B.1: Performance Diagnosis Tools
We introduce a new technique for automated performance diagnosis, using the program's callgraph. We discuss our implementation of this diagnosis technique in the Paradyn Performance Consultant. Our implementation includes the new search strategy and new dynamic instrumentation to resolve pointer-based dynamic call sites at run-time. We compare the effectiveness of our new technique to the previous version of the Performance Consultant for several sequential and parallel applications. Our results show that the new search method performs its search while inserting dramatically less instrumentation into the application, resulting in reduced application perturbation and consequently a higher degree of diagnosis accuracy.
This article presents a class library for detecting typical performance problems in event traces of MPI applications. The library is implemented using the powerful high-level trace analysis language EARL and is embedded in the extensible tool component EXPERT described in this paper. One of EXPERT's essential features is a flexible plug-in mechanism which allows the user to easily integrate performance problem descriptions specific to a distinct parallel application without modifying the tool component.
This paper describes Pajé, an interactive visualization tool for displaying the execution of parallel applications where a (potentially) large number of communicating threads of various life-times execute on each node of a distributed memory parallel system. Pajé is capable of representing a wide variety of interactions between threads. The main novelty of Pajé is an original combination of three of the most desirable properties of visualisation tools for parallel programs: extensibility, interactivity and scalability. This article mainly focuses on the extensibility property of Pajé. To be easier to extend, Pajé was designed as a data-flow graph of modular components, most of them being independent of the semantics of the parallel programming model of the visualized parallel programs. In addition, application programmers can tailor the visualization to their needs, without having to know any insight nor to modify any component of Pajé.
Session
02-B.2: Performance Prediction and Analysis
We present a hybrid version of two previous models that perform analysis of memory hierarchies. The original statistical model provides insight into code performance by statistically analyzing the differing parameters across two similar machines. By focusing on statistical differences, the original model provides the ability to isolate performance degradation causes. The original empirical model provides insight into code performance by empirically inferring the stall time actually incurred within codes due to non-overlapped memory accesses. In this way, it quantifies the performance gain and loss due to recently introduced latency hiding techniques. In these ways, both methods have been used to dissect the execution time of scientific applications. In this paper, we combine the positive attributes of both models by interleaving the analysis methods. Furthermore, we analytically link the models to provide a more focused method for analyzing performance contributions due to latency hiding techniques such as outstanding misses and speculative execution.
This paper describes a toolset, PACE, that provides detailed predictive performance information throughout the implementation and execution stages of an application. It is structured around a hierarchy of performance models that describes distributed computing systems in terms of its software, parallelisation and hardware components, providing performance information concerning expected execution time, scalability and resource use of applications. A principal aim of the work is to provide a capability for rapid calculation of relevant performance numbers without sacrificing accuracy. The predictive nature of the approach provides both pre- and post- implementation analyses, and allows implementation alternatives to be explored prior to the commitment of an application to a system. Because of the relatively fast analysis times, these techniques can be used at run-time to assist in application steering and efficient management of the available system resources.
This paper addresses the problem of estimating the total execution time of a parallel program based domain decomposition. When the execution time of each processor may vary, the total execution time is non-deterministic, specially if the communication to exchange boundary data is asynchronous. We consider the situation where a single iteration on each processor can take two different execution times. We show that the total time depends on the topology of the interconnection network and provide a lower bound for the ring and the grid. This analysis is supported further by a set of simulations and comparisons of specific cases.
Session
05-B.1
There is an increasing interest in asynchronous replica management protocols in which database transactions are executed locally, and the effects of these transactions are incorporated asynchronously on remote database copies. However, the asynchronous protocols currently in use either do not guarantee consistency and serializability as needed by transactional semantics or they impose restrictions on placement of data and on which data objects can be updated. In this paper we investigate an epidemic update protocol that guarantees consistency and serializability in spite of a write-anywhere capability and conduct simulation experiments to evaluate this protocol. Our results establish that this epidemic approach is indeed a viable alternative to traditional eager update protocols for a distributed database environment where consistency and full serializability are needed.
We investigate the design of a coordinator for a cluster of databases. We consider the following alternatives: TP-Heavy using the TUXEDO TP-monitor, TP-Lite with the ORACLE 8 database system, and a TP-Less coordinator implemented in Embedded SQL/C++. In more detail, assuming full replication, we investigate the scalability characteristics of the design alternatives with regard to parallel synchronous replication management. It turns out that the TP-Less approach outperforms commercial TP-middleware for small cluster sizes already. Another observation is that synchronous actions within asynchronous two-level transactions should be avoided.
We present the concept and implementation of a communication infrastructure for a distributed database system. Within this model we use system components that build a federated multi agent systems (MASs).This work evolved as part of the AQuES project, an agent-based database query evaluation system. First we briefly describe basic concepts for MAS architectures which were smoothly integrated within our new model.Second, we present those parts of the message transport layer which provide an ``easy to handle'', scalable architecture based on the ``p&p'' building block principle. Furthermore we show how the query answering process can be broken up into parts of a complex dialog among distributed subagents. We present a generic dialog manager as part of the message transport layer that enables each individual agent to communicate with the system in multiple concurrent threads of execution. Based on this concept, AQuES agents keep track of the complex evaluation environment in a dynamic, multi-query scenario. Finally, we use a query execution example that demonstrates the communication flow of messages that occurs within and among the AQuES federations.
Design and implementation of a large-scale online/real-time information system for the foreign exchange section of a major world-wide bank, used by hundreds of traders, is described. From the system designer's view, this is a large-scale distributed client/server application. It is shown, how much the specific requirements of data replication and parallel processing matched with the paradigms and features of common off-the-shelp components and why proprietary implementation sometimes seemed inevitable. It is further shown, how the properties of the application, combined with performance requirements, lead to the specific distribution of functionality and processing between the client and server side, resulting in an interesting new calculation scheme on the client side. Some important lessons learnt are reported.
Session
18-B.2
Multicasting large amounts of data efficiently to all nodes of a PC cluster is an important operation. In the form of a partition cast it can be used to replicate entire software installations by cloning. Optimizing a partition cast for a given cluster of PCs reveals some interesting architectural tradeoffs, since the fastest solution does not only depend on the network speed and topology, but remains highly sensitive to other resources like the disk speed, the memory system performance and the processing power in the participating nodes. We present an analytical model that guides an implementation towards an optimal configuration for any given PC cluster. The model is validated by measurements on our cluster using Gigabit- and Fast Ethernet links. The resulting simple software tool, Dolly, can replicate an entire 2 GB Windows NT image onto 24 machines in less than 5 minutes.
As SMP clusters are emerging to be attractive platforms for parallel processing, it is natural to extend the convenient shared address programming model of SMP with software DSM on SMP clusters. This paper introduces an SMP protocol for the home-based software DSM system JIAJIA. In the protocol, intra-node processes in an SMP node share their home pages through hardware coherent sharing so as to take the full advantage of the home effect of home-based software DSMs, i.e., the ability to dispense with page faults for references made by the home node of a given page. In contrast, cached remote pages of a process are not shared by its intra-node partners for the similar reason of separate hardware caches in processors of an SMP. Besides, JIAJIA also implements the shared memory communication among processes within the same SMP node to accelerate intra-node communication. Performance evaluation with some well accepted benchmarks and real applications in a cluster of four two-processor nodes shows that the SMP protocol of JIAJIA reduces remote accesses, diffs, and consequently message amounts in all of the ten benchmarks and as a result obtains noticeable performance improvement in seven.
A framework for cluster management is proposed that enables a cluster to be more efficiently utilized within a research environment. It does so by removing cluster management to a management node, leaving the compute nodes as essentially bare machinery. Users may schedule access to one or more of the compute nodes via the management node. At the scheduled time, a previously-saved image of their research environment will be loaded, and the session begun. At the end of the session the user may save a new image of the environment on the management node, to be reloaded at another time. Thus the user may work with a customized environment, which may even be a fledgling operating system, without fear of interference to other researchers. This enables the capital investment of a systems research cluster to be amortized over a greater number of researchers.
Session
03-B.1
Task scheduling in a preemptive runtime environment has potential advantages over the non-preemptive case such as better processor utilization and more flexibility when scheduling tasks. Furthermore, preemptive approaches may need less runtime support (e.g. no task ordering required). In contrast to the non-preemptive case, preemptive task scheduling in a distributed system has not received much attention. In this paper we present a low-cost algorithm, called the Preemptive Task Scheduling algorithm (PTS), which is intended for compile-time scheduling of coarse-grain problems in a preemptive distributed-memory system. We show that we can obtain performance comparable to the performance of non-preemptive algorithms on non-preemptive systems. However, the advantage of using our scheme is that the runtime support for our approach is much simpler, since no task ordering is necessary.
Many load balancing algorithms balance the load according to a topology. Its choice can significantly influence the performance of the algorithm. We consider the two phase balancing model. The first phase calculates a balancing flow with respect to this topology by a diffusion scheme. Its time requirement depends on the maximum node degree and on the number of eigenvalues of the network. The second phase migrates the load according to this flow. A small flow volume and a small diameter of the graph keeps the time requirement of this phase low. We compare and propose several network topologies based on these measurements. Several experiments on a Cray T3E and on a cluster of PCs confirm our cost functions for both balancing phases.
We consider the problem of scheduling trees on two identical processors in order to minimize the makespan. We assume that tasks have unit execution times, and arcs are associated with large identical communication delays. We prove that the problem is NP-hard in the strong sense even when restricted to the class of binary trees, and we provide a polynomial-time algorithm for complete binary trees.
Session
03-B.2
Sequential multi-constraint graph partitioning algorithms have been developed to address the load balancing requirements of multi-phase simulations. The efficient execution of large multi-phase simulations on high performance parallel computers requires that the multi-constraint partitionings are computed in parallel. This paper presents a parallel formulation of a recently developed multi-constraint graph partitioning algorithm. We describe this algorithm and give experimental results conducted on a 128-processor Cray T3E. We show that our parallel algorithm is able to efficiently compute partitionings of similar quality to serial multi-constraint algorithms, and can scale to very large graphs.
We present results of a series of experiments with parallel processing divisible tasks on various cluster of workstations platforms. Divisible task is a new model of scheduling distributed computations. It is assumed that the parallel application can be divided into parts of arbitrary sizes and the parts can be processed independently on distributed computers. The experiments were performed on various applications and distributed computing platforms. Though practical verification of the divisible task scheduling model was the primary goal of the experiments also an insight into the behavior and performance of cluster computing platforms has been gained.
The optimal assignment of computations to processors is a crucial factor determining the effectiveness of a parallel algorithm. We analyze the problem of finding the optimal mapping of a pipeline algorithm on a ring of processors. There are too many variables to consider, the number of virtual processes to be simulated by a physical processor and the size of the packets to be communicated. We provide an analytical model for an optimal approach to these elements. The low errors observed and the simplicity of our proposal makes this mechanism suitable for its introduction in a parallel tool that com-pute the parameters automatically at running time.
Visualization and Computational Steering in Heterogeneous Computing Environments
Sabine Rathmayer
A Web-Based Finite Element Meshes Partitioner and Load Balancer
Ching-Jung Liao
A Framework for an Interoperable Tool Environment
Radu Prodan, John M. Kewley
ToolBlocks: An Infrastructure for the Construction of Memory Hierarchy Analysis Tools
Timothy Sherwood, Brad Calder
Topic 01: Support Tools and Environments
A Preliminary Evaluation of FINESSE, a Feedback-Guided Performance Enhancement System
Nandini Mukherjee, Graham D. Riley, John R. Gurd
On Combining Computational Differentiation and Toolkits for Parallel Scientific Computing
Christian H. Bischof, H. Martin Bücker, Paul D. Hovland
Generating Parallel Program Frameworks from Parallel Design Patterns
Steve MacDonald, Duane Szafron, Jonathan Schaeffer, Steven Bromling
Topic 19:
Metacomputing
Topic 19: Metacomputing
Request Sequencing: Optimizing Communication for the Grid
Dorian C. Arnold, Dieter Bachmann, Jack J. Dongarra
An Architectural Meta-Application Model for Coarse Grained Metacomputing
Stephan Kindermann, Torsten Fink
Topic 19: Metacomputing
Javelin 2.0: Java-Based Parallel Computing on the Internet
Michael O. Neary, Alan Phipps, Steven Richman, Peter Cappello
Data Distribution for Parallel CORBA Objects
Tsunehiko Kamachi, Thierry Priol, Christophe René
ACCESS: Access to CESCA and CEPBA Supercomputing Facilities through EC Framework V sponsorship
Josep L. Larriba-Pey
Topic 03:
Scheduling and Load Balancing
Topic 03: Scheduling and Load Balancing
A Hierarchical Approach to Irregular Problems
Fabrizio Baiardi, Primo Becuzzi, Sarah Chiti, Paolo Mori, Laura Ricci
Load Scheduling with Profile Information
Götz Lindenmaier, Kathryn S. McKinley, Olivier Temam
Neighbourhood Preserving Load Balancing: A Self-Organizing Approach
Attila Gürsoy, Murat Atun
Topic 03: Scheduling and Load Balancing
The Impact of Migration on Parallel Job Scheduling for Distributed Systems
Yanyong Zhang, Hubertus Franke, Jose Moreira, Anand Sivasubramaniam
Memory Management Techniques for Gang Scheduling
William Leinberger, George Karypis, Vipin Kumar
Exploiting Knowledge of Temporal Behaviour in Parallel Programs for Improving Distributed Mapping
Concepció Roig, Ana Ripoll, Miquel A. Senar, Fernando Guirado, Emilio Luque
Topic 07:
Applications on High-Performance Computers
Topic 07: Applications on High-Performance Computers
An Efficient Algorithm for Parallel 3D Reconstruction of Asymmetric Objects from Electron Micrographs
Robert E. Lynch, Hong Lin, Dan C. Marinescu
Fast Cloth Simulation with Parallel Computers
Sergio Romero, Luis F. Romero, Emilio L. Zapata
The Input, Preparation and Distribution of Data for Parallel GIS Operations
Gordon J. Darling, Terence M. Sloan, Connor Mulholland
Study of the Load Balancing in the Parallel Training for Automatic Speech Recognition
El Mostafa Daoudi, Pierre Manneback, Abdelouafi Meziane, Yahya Ould Mohamed El Hadj
Topic 07: Applications on High-Performance Computers
Pfortran and Co-Array Fortran as Tools for Parallelization of a Large-Scale Scientific Application
Piotr Bala, Terry W. Clark
Sparse Matrix Structure for Dynamic Parallelisation Efficiency
Markus Ast, Cristina Barrado, José M. Cela, Rolf Fischer, Jesús Labarta, Óscar Laborda, Hartmut Manz, Uwe Schulz
A Multi-color Inverse Iteration for a High Performance Real Symmetric Eigensolver
Ken Naono, Yusaku Yamamoto, Mitsuyoshi Igai, Hiroyuki Hirayama, Nobuhiro Ioki
Parallel Implementation of Fast Hartley Transform (FHT) in Multiprocessor Systems
Felicia Ionescu, Andrei Jalba, Mihail Ionescu
Topic 10:
Programming Languages, Models and Methods
HPF vs. SAC - A Case Study
Clemens Grelck, Sven-Bodo Scholz
Developing a Communication Intensive Application on the EARTH Multithreaded Architecture
Kevin B. Theobald, Rishi Kumar, Gagan Agrawal, Gerd Heber, Ruppa K. Thulasiram, Guang R. Gao
On the Predictive Quality of BSP-Like Cost Functions for NOWs
Mauro Bianco, Geppino Pucci
Exploiting Data Locality on Scalable Shared Memory Machines with Data Parallel Programs
Siegfried Benkner, Thomas Brandes
Topic 10: Programming Languages, Models and Methods
The Skel-BSP Global Optimizer: Enhancing Performance Portability in Parallel Programming
Andrea Zavanella
A Theoretical Framework of Data Parallelism and its Operational Semantics
Philippe Gerner, Eric Violard
A Pattern Language for Parallel Application Programs
Berna L. Massingill, Timothy G. Mattson, Beverly A. Sanders
Oblivious BSP
J. A. Gonzalez, C. Leon, F. Piccoli, M. Printista, J. L. Roda, C. Rodriguez, F. Sande
A Software Architecture for HPC Grid Applications
Steven Newhouse, Anthony Mayer, John Darlington
Topic 14:
Instruction-Level Parallelism and Processor Architecture
On the Performance of Fetch Engines Running DSS Workloads
Carlos Navarro, Alex Ramírez, Josep-L. Larriba-Pey, Mateo Valero
Cost-Efficient Branch Target Buffers
Jan Hoogerbrugge
Two-Level Address Storage and Address Prediction
Enric Morancho, José María Llabería, Àngel Olivé
Hashed Addressed Caches For Embedded Pointer Based Codes
Marian Stanca, Stamatis Vassiliadis, Sorin Cotofana, Henk Corporaal
BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations
Mihai Budiu, Majd Sakr, Kip Walker, Seth Copen Goldstein
General Matrix-Matrix Multiplication Using SIMD Features of the PIII
Douglas Aberdeen, Jonathan Baxter
Redundant Arithmetic Optimizations
Thomas Y. Yéh, Hong Wang
The Decoupled-Style Prefetch Architecture
Kevin D. Rich, Matthew K. Farrens
Exploiting Java Bytecode Parallelism by Enhanced POC Folding Model
Lee-Ren Ton, Lung-Chung Chang, Chung-Ping Chung
Thursday, August 31st, Morning
Topic 02:
Performance Evaluation and Prediction
Topic 02: Performance Evaluation and Prediction
A Callgraph-Based Search Strategy for Automated Performance Diagnosis
Harold W. Cain, Barton P. Miller, Brian J.N. Wylie
Automatic Performance Analysis of MPI Applications Based on Event Traces
Felix Wolf, Bernd Mohr
Pajé: An Extensible Environment for Visualizing Multi-threaded Programs Executions
Jacques Chassin de Kergommeaux, Benhur de Oliveira Stein
Topic 02: Performance Evaluation and Prediction
A Statistical-Empirical Hybrid Approach to Hierarchical Memory Analysis
Xian-He Sun, Kirk W. Cameron
Use of Performance Technology for the Management of Distributed Systems
D.J. Kerbyson, J.S. Harper, E. Papaefstathiou, D.V. Wilcox, G.R. Nudd
Delay Behavior in Domain Decomposition Applications
Marco Dimas Gubitoso, Carlos Humes, Jr.
Topic 05:
Parallel and Distributed Databases and Applications
Topic 05: Parallel and Distributed Databases and Applications
Database Replication Using Epidemic Communication
JoAnne Holliday, Divyakant Agrawal, Amr El Abbadi
Evaluating the Coordination Overhead of Replica Maintenance in a Cluster of Databases
Klemens Böhm, Torsten Grabs, Uwe Röhm, Hans-Jörg Schek
A Communication Infrastructure for a Distributed RDBMS
Michael Stillger, Dieter Scheffner, Johann-Christoph Freytag
Distribution, Replication, Parallelism and Efficiency Issues in a Large-Scale Online/Real-Time Information System for Foreign Exchange Trading
Peter Peinl
Topic 18:
Cluster Computing
Topic 18: Cluster Computing
Partition Cast - Modelling and Optimizing the Distribution of Large Data Sets in PC Clusters
Felix Rauch, Christian Kurmann, Thomas M. Stricker
A New Home-Based Software DSM Protocol for SMP Clusters
Weiwu Hu, Fuxin Zhang, Haiming Liu
Encouraging the Unexpected: Cluster Management for OS and Systems Research
Ronan Cunniffe, Brian A. Coghlan
Topic 03:
Scheduling and Load Balancing
Topic 03: Scheduling and Load Balancing
Preemptive Task Scheduling for Distributed Systems
Andrei Radulescu, Arjan J.C. van Gemund
Towards Optimal Load Balancing Topologies
Thomas Decker, Burkhard Monien, Robert Preis
Scheduling Trees with Large Communication Delays on Two Identical Processors
Foto Afrati, Evripidis Bampis, Lucian Finta, Ioannis Milis
Topic 03: Scheduling and Load Balancing
Parallel Multilevel Algorithms for Multi-constraint Graph Partitioning
Kirk Schloegel, George Karypis, Vipin Kumar
Experiments with Scheduling Divisible Tasks in Clusters of Workstations
Maciej Drozdowski, Pawel Wolniewicz
Optimal Mapping of Pipeline Algorithms
Daniel González, Francisco Almeida, Luz Marina Moreno, Casiano Rodríguez