Concurrency and Computation:Practice and Experience

• This site has been replaced as of June 2006 by Manuscript Central with instructions at my site
• Here are instructions for Grid Workflow Special Issue due June 1 2004 -- CLOSED

This homepage supports referees.

Standard Referee Form

Journal Vision

WILEY Journal Home Page

Editorial Board

Below you will find active abstracts.

Please send email to Geoffrey Fox, gcf@indiana.edu, if you wish to referee any article.

We will send you link to full text online.

Articles under Consideration for Journal

• 2002-2005 Articles
• 2001 Articles
• 2000 Articles

Submitted in 2002-2005 (top)
• The Grid 2002: Architectures, Environments and Applications Book and Special Issue home page
• Here are instructions for 2002 Java Grande/ISCOPE Special Issue due January 15 2003 -- CLOSED
• C588: Coordinating Components in Middleware Systems
  • Abstract:Configuration and coordination are central issues in the design and implementation of middleware systems and are one of the reasons why building such systems is more di.cult and complex than constructing stand-alone sequential programs. Through configuration, the structure of the system is established — which elements it contains, where they are located and how they are interconnected. Coordination is concerned with the interaction of the various components —when an interaction takes place, which parties are involved, what protocols are followed. Its purpose is to coordinate the behaviour of the various components in a way that meets the overall system speci.cation. The open and adaptive nature of middleware systems makes the task of configuration and coordination particularly challenging. We propose a model that can operate in such an environment and enables the dynamic integration and coordination of components through observation of their behaviour.
  • Matthias Radestock, Susan Eisenbach
  • Trans Enterprise Computer Communications, The Lee Valley Tecnopark, Ashley Road London N17 9LN; Department of Computing, Imperial College of Science, Technology and Medicine, London SW7 2BZ, UK
  • sue@doc.ic.ac.uk
  • Received January 8 2002, Comments to Authors April 18 2002, Accepted August 6 2002
• C589: DEADLOCK DETECTION IN MPI PROGRAMS
  • Abstract:Message Passing Interface (MPI) is commonly used to write parallel programs for distributed memory parallel computers. MPI-CHECK is a tool developed to aid in the debugging of MPI programs that are written in free or fixed format Fortran 90 and Fortran 77. This paper presents the methods used in MPI-CHECK 2.0 to detect many situations where actual and potential deadlocks occur when using blocking and non-blocking point-to-point routines as well as when using collective routines.
  • Glenn Luecke, Yan Zou, James Coyle, Jim Hoekstra, Marina Kraeva
  • High Peformance Computing Group Iowa State University, Ames, Iowa 50011-2251
  • grl@iastate.edu
  • Received January 22 2002, Comments to Authors April 18 2002, accepted May 29 2002
• C590: Research Agenda for the Semantic Grid: A Future e-Science Infrastructure
  • Abstract:e-Science offers a promising vision of how computer and communication technology can support and enhance the scientific process. It does this by enabling scientists to generate, analyse, share and discuss their insights, experiments and results in a more effective manner. The underlying computer infrastructure that provides these facilities is commonly referred to as the Grid. At this time, there are a number of grid applications being developed and there is a whole raft of computer technologies that provide fragments of the necessary functionality. However there is currently a major gap between these endeavours and the vision of e-Science in which there is a high degree of easy-to-use and seamless automation and in which there are flexible collaborations and computations on a global scale. To bridge this practice–aspiration divide, this report presents a research agenda whose aim is to move from the current state of the art in e-Science infrastructure, to the future infrastructure that is needed to support the full richness of the e-Science vision. Here the future e-Science research infrastructure is termed the Semantic Grid (Semantic Grid to Grid is meant to connote a similar relationship to the one that exists between the Semantic Web and the Web). In more detail, this document analyses the state of the art and the research challenges that are involved in developing the computing infrastructure needed for e-Science. In so doing, a conceptual architecture for the Semantic Grid is presented. This architecture adopts a service oriented perspective in which distinct stakeholders in the scientific process provide services to one another in various forms of marketplace. The view presented in the report is holistic, considering the requirements of e-Science and the e-Scientist at the data/computation, information and knowledge layers. The data, computation and information aspects are discussed from a distributed systems viewpoint and in the particular context of the Web as an established large scale infrastructure. A clear characterisation of the knowledge grid is also presented. This characterisation builds on the emerging metadata infrastructure with knowledge engineering techniques. These techniques are shown to be the key to working with heterogeneous information and also to working with experts and establishing communities of e-Scientists. The underlying fabric of the Grid, including the physical layer and associated technologies, is outside the scope of this document. Having completed the analysis, the report then makes a number of recommendations that aim to ensure the full potential of e-Science is realised and that the maximum value is obtained from the endeavours associated with developing the Semantic Grid. These recommendations relate to the following aspects:
    • The research issues associated with the technical and conceptual infrastructure of the Semantic Grid
    • The research issues associated with the content infrastructure of the Semantic Grid
    • The bootstrapping activities that are necessary to ensure the UK’s grid and e-Science infrastructure is widely disseminated and exemplified
    • The human resource issues that need to be considered in order to make a success of the UK e-Science and grid efforts
    • The issues associated with the intrinsic process of undertaking e-Science
    • The future strategic activities that need to be undertaken to maximise the value from the various Semantic Grid endeavours
  • David De Roure, Nicholas Jennings and Nigel Shadbolt
  • Department of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK
  • dder@ecs.soton.ac.uk
  • Received January 23 2002, Comments to Authors May 29 2002; paper split up and accepted in Grid Special issue July 9 2002
• C591: Feature Extraction and Visualization of Clusters with Parallel Processor from Large-Data Sets from Particle Simulations
  • Abstract:Simulating natural phenomena at greater accuracy results in an explosive growth of data. Large - scale simulations with particles currently involve ensembles consisting of 10^6-10^9 particles in 10^5- 10^6 timesteps. Thus, the data file produced in a single run ranges from tens of gigabytes to hundreds of terabytes. This data bank allows one to reconstruct the spatio-temporal evolution of both the particle system in whole and each particle separately. Realistically, to look at large data set at full resolution at all times is not necessary. We show that the agglomerative clustering technique, based on the mutual nearest neighborhood (MNN) concept, can be easily adapted for efficient visualization of huge data sets from large-scale simulations with particles at different resolution level. We present the parallel algorithm for MNN clustering and its timings on the IBM SP and SGI/Origin 3800 multiprocessor systems. The high efficiency obtained is mainly due to the similarity in the algorithmic structure of MNN clustering and particle methods. We show examples drawn from MNN application in visualization and analysis on the order of a few hundred gigabytes of data from discrete particle simulations, using dissipative particle dynamics and fluid particle model. Besides material sciences, this clustering procedure can be applied to other fields, such as earthquake events and stellar populations in nebula clusters.
  • Krzysztof Boryczko, Witold Dzwinel, David A.Yuen
  • AGH Institute of Computer Science, al. Mickiewicza 30, 30-059, Kraków, Poland; Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, Minnesota 55415-1227, USA
  • dwitek@msi.umn.edu
  • Received January 29 2002, Comments to Authors May 29 2002, Accepted June 14 2002
• C592: The Real-Time Message Passing Interface Standard (MPI/RT-1.1)
  • Abstract:The MPI/RT standard is the product of the work of many people working in an open community standards group over a period of six plus years. The purpose of this archival publication is to preserve the significant knowledge and experience that was developed in real-time message passing systems as a consequence of the R&D e®ort as well as in the specification of the standard. Interestingly, several implementations of MPI/RT (as well as comprehensive test suites) have been created in industry and academia over the period during which the standard was created. MPI/RT is likely to gain adoption interest over time, and this adoption may be driven by the promulgation of the standard including this publication. We expect that, when people are interested in understanding options for reliable, QoS-oriented parallel computing with message passing, MPI/RT will serve as a foundation for such a study, whether or not its complete formalism is accepted into other systems or standards. MPI/RT is an o®shoot of MPI-1, and retains many of the communication patterns of MPI- 1. However, MPI/RT has investigated issues of fine-grain concurrency and highest achievable performance in many ways that were evidently inappropriate for MPI-1 to do in the scientific computing space in which it resides, with its much broader audience. MPI/RT focuses on earlybinding (planned transfer), concurrent message passing, while integrating multiple real-time models: time-based, event-driven, and priority-oriented channels. Group admission control and declarative (deferred early binding) semantics support the goal of hard-real-time for the message-passing component of computation. Importantly, MPI/RT emphasizes the decoupling of message transfer and process/thread scheduling as part of its contribution to parallel processing with QoS. Buffer management and state transition diagrams are also integral to the notion of streaming data into and out of processors in a way that is consistent with QoS, and friendly to zero-copy approaches to communication. MPI/RT has also made strides in the direction of a parallel middleware specification by emphasizing an object-oriented design for the API compared to an object-based API or ad hoc API. The advantages of these are plain in the standard, in that the functionality has useful polymorphic adaptations where needed. Furthermore, the concepts that derive from MPI-1 (such as collective operations) appear as objects in MPI/RT. This modification has allowed for the removal of certain constructs in MPI-1 (such as the communicator), in favor of a specification and implementation phase for objects that describe communication in MPI/RT. Overall, a cleaner, more extensible design exists, which does not utilize more resources per se than those which are needed to admit the required channels for a program. Both offline and online admission control is contemplated, and multiple modes are supported, albeit weakly. MPI/RT-1.1, the standard version described here, does not cover all possible real-time parallel programming possibilities. It is silent concerning process/thread scheduling, so in some sense, still has strong aspects of "best effort," in terms of process scheduling. Leaving process scheduling as an orthogonal concern was intentional, so that the best concepts in these areas would be used in concert with MPI/RT, rather than offering a monolith. Furthermore, MPI/RT-1.1 does not explicitly address mode changes (with guaranteed modechange QoS) between sets of channels, with invariants and non-invariants among the resources consumed. This remains important work for the future. The object-oriented, resource-conscious approach of MPI/RT naturally extends to multiple modes. Work to realize this in a standard or in prototypes remains for future work, although it was discussed and prototyped extensively during standardization. It is interesting to consider whether the connection-oriented, but limited QoS and resource specification of MPI/RT leads to a more scalable or less scalable system environment than that posed by MPI and similar middleware. While connections themselves indicate that resources will be assigned per connection, only those connections that are program-mandated are actually built. By way of contrast, in MPI, it is necessary to offer a virtual all-to-all communication topology, and introduce overheads associated with either the static realization of such a topology, or else the dynamic build-up/tear down of connections in constrained environments seeking to scale. Events over the past six years, involving the evolution of networking technology make MPI/RT as interesting as it was when started, and possibly of more ubiquitous application in the long term. Infiniband, Rapid I/O, 3GIO, and other System Area Network standards are likely to offer rudimentary QoS over time in real applications. Likewise, the production of massively concurrent supercomputers (104 nodes or more), is likely to drive the need for predictable message passing in the runtime aspects of such systems. These events are likely to cause the ideas and concepts defined in this standard to have impact in areas far broader than originally anticipated.
  • Anthony Skjellum, Arkady Kanevsky, Yoginder S. Dandass,Jerrell Wattsy, Steve Paavola ,Dennis Cottel, Greg Henleyz, L. Shane Hebertx, Zhenqian Cui, Anna Rounbehler
  • Mississippi State University; MPI Software Technology, Inc.; Network Appliance; California Institute of Technology; Syracuse University; SKY Computers; SPAWAR Systems Center, US Navy; Raytheon Company; Real-Time Message Passing Interface (MPI/RT) Forum http://www.mpirt.org
  • tony@hpcl.msstate.edu
  • Received February 9 2002, Comments to Authors May 29 2002, accepted December 31 2002
• C593: DYNAMIC CLASS MODEL IN OBJECT-ORIENTED DESIGN
  • Abstract:This paper proposes design with the help of objet-oriented modelling. The class model of designed object can be dynamically changed by a system. Thanks to the specificity of the class model we receive new emergent solutions and a warranty of space sparing. The advantage of the proposed approach is a well-grounded theoretical base and polynomial time of operations. It gives a possibility of practical applications and extensions of proposed model.
  • Marcin Skowron
  • Institute of Computer Science Jagiellonian University Nawojki 11, 30-072 Kraków, Poland
  • Marcin.Skowron.Student@softlab.ii.uj.edu.pl
  • Received 12 February 2002, Comments to Author July 4 2002
  • Full Paper: ../CCPEwebresource/c593skowron/c593skowron.pdf
• C594: A parallel data assimilation model for oceanographic observations
  • Abstract:In this paper we describe the development of a program that aims at the optimal integration of observed data in an oceanographic model describing the water transport phenomena in the Agulhas area at the tip of South Africa. Two parallel implementations, MPI and OpenMP, are described and experiments with respect to speed and scalability on a Compaq AlphaServer SC and an SGI Origin3000 are reported
  • Fons van Hees, Aad J. van der Steen; Peter Jan van Leeuwen
  • Computational Physics, Utrecht University P.O. Box 80195, 3508 TD Utrecht; Institute for Marine and Atmospheric Research Utrecht, Utrecht University P.O. Box 80005, 3508 TA Utrecht
  • A.vanderSteen@phys.uu.nl
  • Received 13 February 2002, Comments to Author July 4 2002, accepted August 6 2002
  • Full Paper: ../CCPEwebresource/c594vandersteen/c594join.pdf
• C595: A Comparison of Task Pools for Dynamic Load Balancing of Irregular Algorithms
  • Abstract:Since a static data distribution does not give satisfactory results for parallel irregular algorithms, there is need for a dynamic distribution of data that can be adapted to the current runtime behavior of the algorithm. Task pools are data structures which can distribute data dynamically to different processors.
    This paper discusses the characteristics of task-based algorithms and describes the implementation of selected types of task pools for shared-memory multiprocessors. Several task pools have been implemented in C with POSIX threads and in Java. Results of these implementations measured on three different shared-memory systems are shown for a synthetic algorithm and the parallel hierarchical radiosity method.
  • Matthias Korch and Thomas Rauber
  • Martin-Luther-Universit at Halle-Wittenberg, Fachbereich Mathematik und Informatik, Institut für Informatik D-06099, Halle (Saale), Germany
  • korch@informatik.uni-halle.de
  • Received 26 February 2002, Comments to Author July 4 2002, accepted December 31 2002
  • Full Paper: ../CCPEwebresource/c595korch/c595tplong.pdf
• C596: Towards an Improved Memory Model for Java
  • Abstract:The Java Language Specification contains a collection of rules that describe how a thread's working memory should interact with the main memory in a multi-threaded, shared variables environment. We formalize and analyze the Java memory model rules from the original specification. We are able to remove many unnecessary constraints and show deficiences. We show that sequential consistency does not hold in the original memory model and propose a correction. We also add rules for the prevention of deadlock. Finally we discuss possible compiler optimizations based on our memory model.
  • Vishnu Kotrarajas and Susan Eisenbach
  • Department of Computing, Imperial College, 189 Queen's Gate, London SW7 2BZ, U.K.
  • sue@doc.ic.ac.uk
  • Received 20 March 2002, Comments to Author July 4 2002
• C597: Multi-Wavelength Image Space: Another Grid-Enabled Science
  • Abstract:We describe how the Grid enables new research possibilities in astronomy through multi-wavelength images. To see sky images in the same pixel space, they must be projected to that space, a compute-intensive process. There is thus a virtual data space induced that is defined by an image and the applied projection. This virtual data can be created and replicated with Planners and Replica catalog technology developed under the GriPhyN project. We plan to deploy our system (MONTAGE) on the US Teragrid. Grid computing is also needed for ingesting data -- computing background correction on each image -- which forms a separate virtual data space. Multi-wavelength images can be used for pushing source detection and statistics by an order of magnitude from current techniques; for optimization of multi-wavelength image registration for detection and characterization of extended sources; and for detection of new classes of essentially multi-wavelength astronomical phenomena. The paper discusses both the grid architecture and the scientific goals.
  • Roy Williams, Bruce Berriman, Ewa Deelman, John Good, Joseph Jacob, Carl Kesselman, Carol Lonsdale, Seb Oliver, Thomas A. Prince
  • CACR, California Institute of Technology, USA, IPAC, California Institute of Technology, USA, ISI, University of Southern California, USA, JPL, California Institute of Technology, USA, Astronomy Centre, University of Sussex, UK
  • roy@cacr.caltech.edu
  • Received May 24 2002, Comments to Authors August 6 2002, Accepted August 27 2002
• C605: Guiding RMI Synthesis with Interactive Graph Placement
  • Abstract:CentiJ is a metacomputing system that message forwards through an RMI (Remote Method Invocation) layer for distributed computation by using a bridge pattern code synthesizer. CentiJ reuses original implementations, without altering the source code. It also provides for a means of partitioning a sequential program across a network of workstations (NOWs) by using interactive graph placement. The graph placement algorithms is force-based, treating nodes as charged bodies and arcs as springs. Interaction is used to take advantage of the programmers’ knowledge about a program. The assumption is that the programmer can do a better job at course-grained problem-partitioning than any modern parallelizing compiler.
  • Douglas Lyon
  • Computer Engineering Dept. Fairfield University, Fairfield CT 06430
  • lyon@docjava.com
  • Received June 12 2002, Comments to Author August 14 2002
• C608: A Unified Peer-to-Peer Database Framework and its Application for Scalable Service Discovery
  • Abstract:In a large distributed system spanning many administrative domains such as a DataGrid, it is often desirable to maintain and query dynamic and timely information about active participants such as services, resources and user communities. However, in such a database system, the set of information tuples in the universe is partitioned over one or more distributed nodes, for reasons including autonomy, scalability, availability, performance and security. It is not obvious how to enable general-purpose discovery query support and collective collaborative functionality that operate on the distributed system as a whole, rather than on a given part of it. Further, it is not obvious how to allow for search results that are fresh, allowing dynamic content. It appears that a Peer-to-Peer (P2P) database network may be well suited to support dynamic distributed database search, for example for service discovery. In this paper, we take the first steps towards unifying the fields of database management systems and P2P computing, which so far have received considerable, but separate, attention. We extend database concepts and practice to cover P2P search. Similarly, we extend P2P concepts and practice to support powerful general-purpose query languages such as XQuery and SQL. As a result, we devise the Unified Peer-to-Peer Database Framework (UPDF), which allows to express specific applications for a wide range of data types, node topologies (e.g. ring, tree, graph), query languages (e.g. XQuery, SQL), query response modes (e.g. Routed, Direct and Referral Response), neighbor selection policies (in the form of an XQuery), pipelining, timeout and other scope characteristics.
  • Wolfgang Hoschek
  • CERN IT Division, European Organization for Nuclear Research, 1211 Geneva 23, Switzerland
  • wolfgang.hoschek@cern.ch
  • Received June 21 2002, Comments to Author 14 2002
• C609: The Web Service Discovery Architecture
  • Abstract:An enabling step towards increased Internet software execution exibility is the web services vision of distributed computing where programs are no longer configured with static information. Rather, the promise is that programs are made more flexible and powerful by querying Internet databases (registries) at runtime in order to discover information and network attached third-party building blocks. Services can advertise themselves and related metadata via such databases, enabling the assembly of distributed higher-level components. In this paper, we propose and specify a discovery architecture that supports this vision, the so-called Web Service Discovery Architecture (WSDA). WSDA promotes an interoperable web service layer by defining appropriate services, interfaces, operations and protocol bindings for discovery. It embraces and integrates solid industry standards. It is modular because it defines a small set of orthogonal multi-purpose communication primitives (building blocks) for discovery. These primitives cover service identification, service description retrieval, data publication as well as minimal and powerful query support. Each communication primitive is designed to avoid any unnecessary complexity. WSDA is open and flexible because each primitive can be used, implemented, customized and extended in many ways. It is powerful because the individual primitives can be combined and plugged together by specific clients and services to yield a wide range of behaviors and emerging synergies. It is unified because it subsumes an array of disparate concepts, interfaces and protocols under a single semi-transparent umbrella. It is non-intrusive because it offers interfaces but does not mandate that every service must comply to these interfaces.
  • Wolfgang Hoschek
  • CERN IT Division, European Organization for Nuclear Research, 1211 Geneva 23, Switzerland
  • wolfgang.hoschek@cern.ch
  • Received June 10 2002, Comments to Author June 28 2002, Accepted August 14 2002
• C610: Impact of Mixed-Parallelism on Parallel Implementations of Strassen and Winograd Matrix Multiplication Algorithms
  • Abstract:In this paper we study the impact of the simultaneous exploitation of data- and task-parallelism, so-called mixed parallelism, on Strassen and Winograd matrix multiplication algorithms. For each of these algorithms, we propose two mixed-parallel implementations. The former follows the phases of the original algorithms while the latter has been designed as the result of a list scheduling algorithm. We give a theoretical comparison.
  • F. Desprez and F. Suter
  • LIP, ENS Lyon, 46 allee d'Italie, 69364 Lyon Cedex 07, France
  • Frederic.Desprez@ens-lyon.fr
  • Received July 1 2002, Comments to Author October 21 2002, Accepted July 24 2003
• C614: Smart Data: The Source of - and the Solution to - Security Risks
  • Abstract:Note (from editor) this is a "vision" paper. It is suggested that online data, as it is annotated in the years to come by experts, will incrementally become far more usable by all users, including those who violate security controls. In fact, the main source of security in data, its natural heterogeneity and the resulting difficulty in making use of it, will sharply diminish in the years to come. But this "smartness" of data can also be exploited in order to greatly enhance data security. Further, it is suggested that the development of four different software technologies, if guided by an integrated vision, could serve as a broad-based and powerful platform for the collaborative specification and enforcement of security controls, and for the maintenance of these controls through multiple cycles of data transformation, integration, and reuse.
  • Roger (Buzz) King
  • Dept. of Computer Science, University of Colorado, Boulder CO, 80309
  • roger@cs.colorado.edu
  • Received July 3 2002, Comments to Author October 21 2002, Accepted December 31 2002
• C624: Mobile Agents and Web Databases: Models and Experimentation
  • Abstract:In this paper we present practical experiences gathered from the employment of two popular Java-based mobile-agent platforms, IBM's Aglets and Mitsubishi's Concordia. We present some basic distributed computing models and describe their adaptation to the mobile-agent paradigm. Upon these models we develop a set of frameworks for distributed database access over the World-Wide Web, using IBM's Aglets and Mitsubishi's Concordia platforms. We compare the two platforms both quantitatively and qualitatively. For the quantitative comparison, we propose, employ, and validate an approach to evaluate and analyze mobile-agent framework performance. For the qualitative assessment, we present our observations about the programmability and robustness of, and mobility provided by, the two platforms.
  • G. Samaras, M. Dikaiakos, C. Spyrou
  • Department of Computer Science, University of Cyprus, P.O. Box 20537, 1678 Nicosia, Cyprus
  • cssamara@ucy.ac.cy
  • Received July 11 2002, Comments to Authors December 31 2002
• Cluster 2001 Special Issue: 6 papers in final accepted form at ../CCPEwebresource/c635toc640clustersi
• C641: A Comparison of Concurrent Programming and Cooperative Multithreading under Load Balancing Applications
  • Abstract: Two models of thread execution are the general concurrent programming execution model (CP) and the cooperative multithreading execution model (CM). CP provides nondeterministic process execution where context switches occur arbitrarily. CM provides threads that execute one at a time until they explicitly choose to yield the processor. This paper uses two classic applications to reveal the advantages and disadvantages of load balancing during process execution under CP and CM styles. These applications are programmed in two different languages (SR and Dynamic C) on different hardware (standard PCs and embedded system controllers). An SR-like run-time system, DesCaRTeS, was developed to provide inter-process communication for the Dynamic C implementations. This paper compares load balancing and non- load balancing implementations; it also compares CP and CM style implementations. The results show that: in cases of very high or very low workloads, load balancing slightly hindered performance; and in cases of moderate workload, both SR and Dynamic C implementations of load balancing generally performed well. Further, for these applications, CM style programs outperform CP style programs in some cases, but the opposite occurs in some other cases. This paper also discusses qualitative tradeoffs between CM style programming and CP style programming for these applications.
  • Justin T. Maris, Aaron W. Keen, Takashi Ishihara, and Ronald A. Olsson
  • Department of Computer Science, University of California, Davis, CA 95616 USA
  • olsson@cs.ucdavis.edu
  • Received July 31 2002, Comments to Authors December 31 2002, Accepted February 14 2003
• C642 (Performance Section): Comparing the Performance of MPICH with Cray's MPI and with SGI's MPI
  • Abstract: The purpose of this paper is to compare the performance of MPICH with the vendor MPI on a Cray T3E-900 and an SGI Origin 3000. Seven basic communication tests which include basic point-to-point and collective MPI communication routines were chosen to represent commonly used communinication patterns. Cray's MPI performed better (and sometimes significantly better) than MSU's MPICH for small and medium messages. They both performed about the same for the large messages. However for 3 tests MSU's MPICH was about 20 percent faster than Cray's MPI. SGI's MPI performed and scaled better (and sometimes significantly better) than MPICH for all messages, except for the scatter test where MPICH outperformed SGI's MPI for 1 Kbyte messages. The poor scalability of MPICH on the Origin 3000 suggests there may be scalability problems with MPICH.
  • Glenn R. Luecke, Marina Kraeva, Lili Ju
  • Iowa State University Ames Iowa
  • grl@iastate.edu
  • Received 16th October 2001, Revised 2nd July 2002, Accepted 1st Aug 2002
• C643 (Performance Section): A Scalable HPF Implementation of a Finite Volume CEM Application on a CRAY T3E Parallel System
  • Abstract: The time-dependent Maxwell equations are one of the most important approaches to describing dynamic or wide-band frequency electromagnetic phenomena. A sequential nite volume, characteristic-based procedure for solving the time-dependent, three-dimensional Maxwell equations has been implemented in Fortran successfully before. Due to its large requirement of memory space and high demand of CPU time, it is impossible to test the code with large array size. Hence, it is essential to implement the code on a parallel computing system. In this paper, we discuss an eÆcient and scalable parallelization of the sequential Fortran time-dependent Maxwell equations solver using High Performance Fortran (HPF). The background of the project, the theory behind the efficiency being achieved, the parallelization methodologies employed, and the experimental results obtained on the Cray T3E massively parallel computing system will be described in detail. Experimental runs show that the execution time is reduced drastically through parallel computing. The code is scalable up to 98 processors on the Cray T3E and has a similar performance compared to an MPI implementation. Based on the experimentation carried out in this research, we believe that a high level parallel programming language such as High Performance Fortran is a fast, viable and economical approach to parallelizing many existing sequential codes which exhibit a lot of parallelism.
  • Yi Pan, Joseph J.S. Shang and Minyi Guo
  • Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA; Air Vehicle Directorate Air Force Research Laboratory WPAFB, OH 45433-7521, USA; Department of Computer Software, The University of Aizu, Aizu-Wakamatsu City, Fukushima 965-8580 Japan
  • pan@cs.gsu.edu
  • Received 16th October 2001, Revised 1st August 2002, Accepted 8th Aug 2002
• C650: A Summary of Grid Computing Environments
  • Abstract: This short paper summarizes a set of 28 papers gathered together by the GCE (Grid Computing Environment) group of the Global Grid Forum. This set is published in 2002 as a special issue of Concurrency and Computation: Practice and Experience. The papers are listed at the end of this report together with associated papers in a Grid Computing book
  • Geoffrey Fox, Dennis Gannon, Mary Thomas
  • Department of Computer Science, 215 Lindley Hall,150 S. Woodlawn Ave,. Bloomington IN 47405-7104; Texas Advanced Computing Center, The University of Texas at Austin, 10100 Burnet Road, Austin, Texas 78758
  • gcf@indiana.edu
  • Accepted August 6 2002
  • Full Paper: ../CCPEwebresource/c650gridgcespcissueoverview/c650gcesurvey.pdf
• C651: OpenMP-Oriented Applications for Distributed Shared Memory Architectures
  • Abstract: The fast emergence of OpenMP as the preferable parallel programming paradigm for small-to-medium scale parallelism could decline unless OpenMP will show capabilities to be the model-of-choice for large scale high performance parallel computing of the next decade. The main stumbling block from adapting OpenMP for distributed shared memory (DSM) machines, which are based on architecture like cc-NUMA, stems from the absence of capabilities for data placement among processors and threads for achieving data locality. The absence of such mechanism causes remote memory accesses and inefficient cache memory use, both of which lead to poor performance. This paper presents a simple software programming approach called Copy-inside-Copy-back (CC) that exploits the privatization mechanism of OpenMP for data placement and re-placement. This technique enables one to distribute data without taking the control and the exibility from the programmer, and thus, is an alternative to the traditional implicit and explicit approaches. Moreover, the CC approach enables SPMD style of programming that makes the development process of an OpenMP application more structured, and simply to modify and debug. The CC technique was tested and analyzed using the NAS Parallel Benchmarks on SGI Origin 2000 multiprocessors machine. The lesson learnt from this study shows that OpenMP can deliver the desired large- scale parallelism although fast copy mechanism is essential.
  • Ami Marowka, Zhenying Liu, Barbara Chapman
  • Department of Computer Science, The University of Houston, Texas
  • amimar2@yahoo.com
  • Received August 9 2002, Comments to Authors December 31 2002, Accepted February 14 2003
• C652: Parallel Operation of CartaBlanca on Shared and Distributed Memory Computers
  • Abstract:We describe the parallel performance of the pure Java CartaBlanca code on heat transfer and multiphase fluid flow problems. CartaBlanca is designed for parallel computations on partitioned unstructured meshes. It uses Java’s thread facility to manage computations on each of the mesh partitions. Inter-partition communications are handled by two compact objects for node-by-node communication along partition boundaries and for global reduction calculations across the entire mesh. For distributed calculations, the JavaParty package from the University of Karlsruhe is demonstrated to work with CartaBlanca.
  • N. T. Padial-Collins, W. B. VanderHeyden, D. Zhang, E. D. Dendy, D. Livescu
  • Los Alamos National Laboratory Theoretical Division and Los Alamos Computer Science Institute Los Alamos, NM 87545
  • nelylanl@lanl.gov
  • Received August 13 2002, Comments to Authors December 31 2002, Accepted January 12 2003
• C653: Parallel Program Debugging by Specification
  • Abstract:Most message passing parallel programs employ logical process topologies with regular characteristics to support their computation. Since process topologies define the relationship between processes, they present an excellent opportunity for debugging. The primary benefit is that process behaviours can be correlatred, allowing expected behaviour to be abstracted and identified, and undesirable behaviour reported. However topology support is inadequate in most message parallel programming environments, including the popular Message Passing Interface (MPI) and the Parallel Virtual Machine (PVM). Programmers are forced to implement topology support themselves, increasing the possibility of introducing errors.
    This paper introduces a trace- and topology-based contract-like approach to parallel program debugging, driven by four distinct types of specification. Trace interpretation specifications allow trace data from a variety of sources and message passing libraries.to be interpreted in an abstract manner, and topology specifications address the lack of explicit topology knowledge, and facilitate the construction of user-consistent views of the debugging activity. Loop specifications express topology-consistent views of the debugging activity, allowing conformance testing of associated trace data, and error specifications specify undesirable event interactions, including mismatched message sizes and mismatched communication pairs. Both loop and error specifications are simplified by having knowledge of the actual topologies being debugged.
    The wealth of new debugging views and techniques made possible by our contract-like approach are also discussed.
  • Simon Huband and Chris McDonald
  • Department of Computer Science and Software Engineering, The University of Western Australia, Crawley, Western Australia 6009, Australia.
  • huey@csse.uwa.edu.au
  • Received August 16 2002, Comments to Authors December 31 2002, Accepted March 2 2003
• C655: Improving the official specification of Java bytecode verification
  • Abstract: Bytecode verification is the main mechanism to ensure type safety in the Java Virtual Machine. Inadequacies in its official specification may lead to incorrect implementations where security can be broken and/or certain legal programs are rejected. This paper provides a comprehensive analysis of the specification along with concrete suggestions for improvement.
  • Alessandro Coglio
  • Kestrel Institute, 3260 Hillview Avenue, Palo Alto, CA 94304, USA
  • coglio@kestrel.edu
  • Received 8 January 2002, Revised 4 August 2002, Accepted August 15 2002
• C658: Modular specification of frame properties in JML
  • Abstract:We present a modular specification technique for frame properties. The technique uses modifies clauses and abstract fields with declared dependencies. Modularity is guaranteed by a programming model that enforces data abstraction by preventing representation and argument exposure, a semantics of modifies clauses that uses a notion of ``relevant location,'' and by modularity rules for dependencies. For concreteness, we adapt this technique to the Java Modeling Language, JML.
  • P. Muller, A. Poetzsch-Heffter, and G. T. Leavens
  • Dept. of Computer Science, Iowa State University, 229 Atanasoff Hall, Ames, Iowa, 50011-1040, USA
  • leavens@cs.iastate.edu
  • Received October 1 2001, Revised October 2 2002, Accepted October 5 2002
• C659: Parallel LU Factorization of Sparse Matrices on FPGA-Based Configurable Computing Engines
  • Abstract:Reconfigurable computing has demonstrated in the last decade capability to significantly improve the performance of a wide range of computation-intensive applications. With steady advances in silicon technology, as predicted by Moore's law, Field-Programmable Gate Array (FPGA) technologies have enabled the implementation of System-On-a Programmable-Chip (SOPC) computing platforms, which, in turn, have given a significant boost to the field of reconfigurable computing. It is possible now to implement various specialized parallel machines within one silicon die. For example, LU factorization is widely used in engineering and science to solve efficiently large systems of linear equations. In this paper, we describe our design and implementation of a parallel machine on an SOPC development board, using multiple copies of the Altera soft configurable processor, namely Nios(r); we use this machine for LU factorization. Our implementation facilitates the efficient solution of linear equations at a cost much lower than that of supercomputers and networks of workstations. The intricacies of our FPGA-based design are presented along with tradeoff choices made for the purpose of illustration. Performance results prove the viability of our approach.
  • Xiaofang Wang and Sotirios G. Ziavras
  • Department of Electrical and Computer Engineering New Jersey Institute of Technology University Heights Newark, New Jersey 07102, USA
  • ziavras@njit.edu
  • Received October 19 2002, Comments to Authors December 31 2002, Accepted January 17 2003
• C660: Frameworks for Incorporating Semantic Relationships into Object-Oriented Database Systems
  • Abstract: A semantic relationship is a data modeling construct that connects a pair of classes or categories and has inherent constraints and other functionalities that precisely reflect the characteristics of the specific relationship in an application domain. Examples of semantic relationships include part-whole, ownership, materialization, and role-of. Such relationships are important in the construction of information models for advanced applications, whether one is employing traditional data modeling techniques, knowledge-representation languages, or object-oriented modeling methodologies. This paper focuses on the issue of providing built-in support for such constructs in the context of object-oriented database (OODB) systems. Most of the popular object-oriented modeling approaches include some semantic relationships in their repertoire of data modeling primitives. However, commercial OODB systems, which are frequently used as implementation vehicles, tend not to do the same. We will present two frameworks by which a semantic relationship can be incorporated into an existing OODB system. The first only requires that the OODB system support manifest type with respect to its instances. The second assumes that the OODB system has a special kind of metaclass facility. The two frameworks are compared and contrasted. In order to ground our work in existing systems, we show the addition of a part-whole semantic relationship both to the ONTOS DB/Explorer OODB system and the VODAK Model Language (VML).
  • Michael Halper, Li-min Liu, James Geller, and Yehoshua Perl
  • Dept. of Mathematics & Computer Science, Kean University, Union, NJ 07083 USA; Dept. of Applied Mathematics Chung Yuan Christian University, Chung-Li, Taiwan; CS Dept. NJIT Newark, NJ 07102 USA
  • mhalper@kean.edu
  • Received February 15 2002, Revised October 28 2002, Accepted November 2 2002
• C661: Enhancing OODB Semantics to Support Browsing in an OODB Vocabulary Representation
  • Abstract: In previous work, we have modeled a vocabulary given as a semantic network by an OODB (Object-Oriented Database). The OODB schema thus obtained provides a compact abstract view of the vocabulary. This enables fast traversal of the vocabulary by a user. In the semantic network vocabulary, the IS-A relationships express the specialization hierarchy. In our OODB modeling of the vocabulary, the SUBCLASS relationship expresses the specialization hierarchy of the classes and supports the inheritance of their properties. A typical IS-A path in the vocabulary has a corresponding shorter SUBCLASS path in the OODB schema. In the current paper we expose several cases where the SUBCLASS hierarchy fails to fully correspond to the IS-A hierarchy of the vocabulary. In these cases there exist traversal paths in the semantic network for which there are no corresponding traversal paths in the OODB schema. The reason for this failure is the existence of some IS-A relationships between concepts of two classes, that are not connected by a SUBCLASS relationship. This phenomenon weakens the accuracy of our modeling. To rectify the situation we introduce a new OODB semantic relationship IS-A' to represent the existence of IS-A relationships between concepts of a pair of classes which are not connected via a SUBCLASS relationship. The resulting schema contains both SUBCLASS relationships and IS-A' relationships which completely models the IS-A hierarchy of the vocabulary. We define a mixed class level traversal path to contain either SUBCLASS or IS-A' relationships. Consequently, each traversal path in the semantic network has a corresponding mixed traversal path in the OODB schema. Hence the introduction of the semantic OODB IS-A' relationship improves the modeling of semantic network vocabularies by OODBs.
  • Li-min Liu, James Geller and Yehoshua Perl
  • Department of Applied Mathematics,Chung Yuan Christian University 22, Pu-Zen, Pu-Chung Li, Chung-Li, Taiwan, R.O.C.; Computer Science Department, New Jersey Institute of Technology, Newark, NJ 07102 USA
  • thescientist00@yahoo.com
  • Received February 22 2002, Revised October 30 2002, Accepted November 2 2002
• C662: Efficient Parallel Implementations of Unstructured Mesh Generation with High Performance Fortran
  • Abstract:Unstructured mesh generation exposes highly irregular computation patterns, which imposes a challenge in implementing triangulation algorithms on parallel machines. This paper reports on an efficient parallel implementation of locally Delaunay triangulation with High Performance Fortran (HPF). Our algorithm exploits embarrassing parallelism by performing sub-block triangulation and boundary merge independently at the same time. The sub-block triangulation is by a divide and conquer Delaunay algorithm known for its sequential efficiency, and the boundary triangulation is by an incremental construction algorithm with low overhead. Compared to prior work, our parallelization method is both simple and efficient. In the paper, we also describe a solution to the collinear points problem that usually arises in large data sets. Our experiences with the HPF implementation show that with careful control of the data distribution, we are able to parallelize the program using HPF's standard directives and extrinsic procedures. Experimental results on several parallel platforms, including an IBM SP2 and a DEC Alpha farm, show that a parallel efficiency of 31%-66% can be achieved for an 8-node distributed memory system. We also compare efficiency of the HPF implementation to that of a similarly hand-coded MPI implementation.
  • Min-Bin Chen, Tyng-Ruey Chuang and Jan-Jan Wu
  • Department of Management Information Systems, Chung Kuo Institute of Technology, Mucha, Taipei 116, Taiwan; Institute of Information Science, Academia Sinica, Nankang, Taipei
  • cmb@mail.ckitc.edu.tw
  • Received November 23 2002, Comments to Authors March 8 2003, Revised June 17 2003, Accepted July 25 2003
• C663: A PC Cluster System Employing the IEEE 1394
  • Abstract:In this paper, we describe the design and evaluation of a PC cluster system in which IEEE 1394 is applied. Networks for parallel cluster computing require low latency and high bandwidth. It is also important that the networks be commercially available at low cost. Few network devices satisfy all of the above requirements. However, the IEEE 1394 standard provides a good compromise for fulfilling these requirements. We have used IEEE 1394, which supports a 400 Mbps data transfer rate, to connect the nodes of a PC cluster system which we have designed and implemented. We have implemented two communication libraries. One is a fast communication library called CF for IEEE 1394. The other is an MPI layer library on the CF library. Experimental results show that CF achieves a 17.2 microsecond round-trip time. On application benchmarks, the system was considerably faster than TCP/IP over Fast Ethernet. Even though the system was constructed at very low cost, it provides good performance. Using the IEEE 1394 standard is thus a good solution for low-cost cluster systems.
  • Kazuki Hyoudou, Ryota Ozaki and Yasuichi Nakayama
  • Department of Computer Science, The University of Electro-Communications Chofu, Tokyo 182-8585 Japan
  • hyoudo-k@igo.cs.uec.ac.jp
  • Received November 29 2002, Comments to Authors March 8 2003, Revised June 9 2003, Accepted July 24 2003
• C664: Data Structures in Java for Matrix Computations
  • Abstract:In this paper it is shown how to utilize Java arrays for matrix computations. We discuss the disadvantages of Java arrays when used as two-dimensional array for dense matrix computation, and how to improve the performance. We show how to create efficient dynamic data structures for sparse matrix computations using Java's native arrays. We construct a data structure for large sparse matrices that is unique for Java. This datastructure is shown to be more dynamic and efficient than the traditional storage schemes for large sparse matrices. Numerical results show that this new data structure, called Java Sparse Array, is competitive with the traditional Compressed Row Storage scheme on matrix computation routines. Java gives increased flexibility without loosing efficiency. Compared to other object oriented data structures it is shown that Java Sparse Arrays has the same flexibility.
  • Geir Gundersen and Trond Steihaug
  • Department of Informatics, University of Bergen, Norway
  • Trond.Steihaug@ii.uib.no
  • Received December 10 2002, Comments to Authors March 8 2003, Revised May 5 2003, Accepted July 24 2003
• C665(Performance Section): Performance and Scalability of MPI on PC Clusters
  • Abstract:The purpose of this paper is to compare the communication performance and scalability of MPI communication routines on an NT cluster, a Myrinet Linux cluster, an Ethernet Linux cluster, a Cray T3E-600, and an SGI Origin 2000. All tests in this paper were run for the various numbers of processors and 2 message sizes. For most of the MPI tests used in this paper, the T3E-600 and Origin 2000 outperform the NT cluster, the Myrinet and Ethernet Linux clusters. In spite of the fact that the Cray T3E-600 is about 5 years old, it performs best of all machines for most of the tests. For mpi_bcast, mpi_allgather, and mpi_alltoall, the Myrinet Linux cluster outperforms the NT cluster. For all other MPI collective routines, the NT cluster outperforms the Myrinet Linux cluster. For all MPI collective routines, the Myrinet Linux cluster performs significantly better than the Ethernet Linux cluster.
  • Glenn R. Luecke, Jing Yuan, Silvia Spanoyannis, Marina Kraeva
  • 292 Durham Center Iowa State University Ames, Iowa 50011, USA
  • grl@iastate.edu
  • Received February 6 2001, Revised November 14 2002, Accepted December 3 2002
  • Full Paper:../CCPEwebresource/c665pemcs16/c665pemcspaper16.pdf
• C666: A role for Pareto optimality in mining performance data
  • Abstract:Improvements in performance modeling and identification of computational regimes within software libraries is a critical first step in developing software libraries that are truly agile with respect to the application as well as to the hardware. It is shown here that Pareto ranking, a concept from multi-objective optimization, can be an effective tool for mining large performance datasets. The approach is illustrated using software performance data gathered using both the public domain LAPACK library and an asynchronous communication library based on IBM LAPI active message library.
  • Joël M. Malard
  • Pacific Northwest National Laboratory Battelle Boulevard, P.O. Box 999 Richland, WA 99352
  • JM.Malard@pnl.gov
  • Received December 31 2002, Comments to Authors March 8 2003, accepted December 30 2003
• C667: A Performance Study of Job Management Systems
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • T. El-Ghazawi1
  • The George Washington University, George Mason University
  • tarek@seas.gwu.edu
  • May 2002, Revised: Dec. 2002, Accepted: Dec. 2002
• C668: Supporting Bulk Synchronous Parallelism with a High Bandwidth Optical Interconnect
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • I. Gourlay
  • Informatics Research Institute, University of Leeds, Leeds LS2 9JT
  • iain@comp.leeds.ac.uk
  • Recieved: May 2002, Revised: Oct. 2002, Accepted: Dec. 2002
• C669: Towards a More Realistic Comparative Analysis of Multicomputer Networks
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • H. Sarbazi-Azad
  • Department of Computing Science, University of Glasgow, Glasgow G12 8QQ.
  • azad@sharif.edu
  • May 2002, Revised: Nov. 2002, Accepted: Dec. 2002
• C670: RF-MVTC: An EÆcient Risk-Free Multiversion Concurrency Control Algorithm
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • A. Boukerche
  • Department of Computer Sciences, University of North of Texas
  • boukerche@cs.unt.edu
  • Recieved: June 2002, Revised: Nov 2002, Accepted: Dec. 2002
• C671: On the Performance of Circuit-Switched Networks in the Presence of Correlated Traffic
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • G. Min
  • Department of Computing, School of Informatics, University of Bradford, Bradford, BD7 1DP, U.K.
  • g.min@brad.ac.uk
  • May 2002, Revised: Dec. 2002, Accepted: Dec. 2002
• C672: Performance Evaluation of a Random-Walk-Based Algorithm for Embedding Dynamically Evolving Trees in Hypercubic Networks
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • K. Li
  • Department of Computer Science, State University of New York, New Paltz, New York 12561-2499
  • li@mcs.newpaltz.edu
  • May 2002, Revised: Oct. 2002, Accepted: Dec. 2002
• C673: On the Scalability of Many-to-many Reliable Multicast Sessions
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • W. Y. Yoon
  • Samsung Advanced Institute of Technology, South Korea
  • wyyoon@sait.samsung.co.kr
  • June 2002, Revised: Dec. 2002, Accepted: Dec. 2002
• C674: One-to-All Broadcasting Scheme for Arbitrary Static Interconnection Networks with Bursty Background Traffic
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • Demetres Kouvatsos
  • Performance Modelling and Engineering Research Group, Department of Computing, University of Bradford BD7 1DP, Bradford, UK
  • d.d.kouvatsos@scm.brad.ac.uk
  • Received October 19 2002
• C675: Editorial on Benchmarking Special Issue
  • Special Issue: International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'02), held in conjunction with IEEE IPDPS 2002, April 15-19, 2002, Fort Lauderdale, USA; editors Mohamed Ould-Khaoua and Geyong Min
  • Mohamed Ould-Khaoua and Geyong Min
  • Glasgow University; Bradford University
  • mohamed@dcs.gla.ac.uk and G.Min@Bradford.ac.ukG.Min@Bradford.ac.uk
  • Received February 16 2003
• C676: Toward the Design of a Parallel, Linear Algebraic System
  • Abstract:We describe a generic, software framework for the solution of linear algebraic systems sufficient to provide for their use in a parallel, iterative context. Some base assumptions about the structure of the underlying problem and problem domain, as well as the initial distribution of the parallel structures are described to provide a framework for the discussion of an implementation using templated C++ code; however, the design has been made sufficiently flexible that it could easily be applied to other implementations of the base data structures.
  • W. D. Turner and J. E. Flaherty
  • Visualization and Computer Vision, GE Global Research, Schenectady, NY 12301; Scientific Computation Research Center, and Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180
  • flahej@rpi.edu
  • Received February13 2003, Comments to Authors April 28 2003
• C677: Linda implementations in Java for concurrent systems
  • Abstract: This paper surveys a number of the implementations of Linda that are available in Java. It provides some discussion of their strengths and weaknesses, and presents the results from benchmarking experiments using a network of commodity workstations. Some extensions to the original Linda programming model are also presented and discussed, together with examples of their application to parallel processing problems.
  • G. C. Wells, A. G. Chalmers, and P. G. Clayton
  • Department of Computer Science, Rhodes University, Grahamstown, 6140, South Africa; Department of Computer Science, University of Bristol, Merchant Venturers Building, Bristol BS8 1UB, U.K.
  • G.Wells@ru.ac.za
  • Received February 13 2003, Comments to Authors April 28 2003, Revised 17 June 2003, Accepted July 24 2003
• C678: Studying Protein Folding on the Grid: Experiences Using CHARMM on NPACI Resources under Legion
  • Abstract:One benefit of a computational grid is the ability to run high-performance applications over distributed resources simply and securely. We demonstrated this benefit with an experiment in which we studied the protein-folding process with the CHARMM molecular simulation package over a grid managed by Legion, a grid operating system. High-performance applications can take advantage of grid resources if the grid operating system provides both low-level functionality as well as high-level services. We describe the nature of services provided by Legion for high-performance applications. Our experiences indicate that human factors continue to play a crucial role in the configuration of grid resources, underlying resources can be problematic, grid services must tolerate underlying problems or inform the user, and high-level services must continue to evolve to meet user requirements. Our experiment not only helped a scientist perform an important study, but also showed the viability of an integrated approach such as Legion’s for managing a grid.
  • Anand Natrajan, Nancy Wilkins-Diehr, Anthony D. Fox, Michael Crowley, Marty A. Humphrey, Andrew S. Grimshaw, Charles L. Brooks III
  • Department of Computer Science University of Virginia; San Diego Supercomputing Center University of California at San Diego; Department of Molecular Biology The Scripps Research Institute
  • an4m@cs.virginia.edu
  • Received February 6 2003, Comments to Author February 6 2003, Revised February 27 2003, Accepted March 2 2003
• C679: Abstracting Asynchronous Object Interaction using First-Class Functions and Continuations in an Event-Driven System
  • Abstract: The shift in focus of distributed computing from local-area networks to geographically-distributed environments highlights the need for new distributed programming models. In this work we explore the combination of a single-threaded event-driven execution model with a small number of concepts traditionally found in functional languages. We describe a distributed programming system, called Orfeo, based on a simple yet powerful procedural language and on asynchronous remote function calls. We discuss how to use continuations and first-class function values to construct several useful control abstractions, showing how a small set of powerful concepts can provide the basis for a highly asynchronous and flexible distributed programming system.
  • Maria Julia de Lima, Noemi Rodriguez, Roberto Ierusalimschy
  • PUC-Rio
  • noemi@inf.puc-rio.br
  • Received March 14 2003, Comments to Authors Oct 7 2003
• C680: Parallel Object-Oriented Framework Optimization
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • Daniel P. Quinlan, Markus Schordan, Brian Miller and Markus Kowarschik
  • Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore CA USA; System Simulation Group, Department of Computer Science, University of Erlangen-Nuremberg, Germany
  • dquinlan@llnl.gov
  • Received Sept 20 2001, Revised May 29 2002, Accepted March 14 2003
• C681: A compiler for multiple memory models
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • S. P. Midkiff, J. Lee and D.A. Padua
  • School of Electrical and Computer Engineering, Purdue University; School opf Computer Science and Engineering, Seoul National University; Department of Computer Science, University of Illinois at Urbana-Champaign
  • smidkiff@purdue.edu
  • Received Sept 20 2001, Revised May 29 2002, Accepted July 1st 2002
• C682: Compiling Data-Parallel Programs for Clusters of SMPs
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • Siegfriend Benkner and Thomas Brandes
  • Institute of Software Science, University of Vienna Austria; Fraunhofer Institute for Algorithms and Scientific Computation, St. augustin Germany
  • sigi@ieee.org
  • Received Sept 20 2001, Revised May 29 2002, Accepted July 1st 2002
• C683: Group-SPMD programming with orthogonal processor groups
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • Thomas Rauber, Robert Reilein and Gudula Runger
  • Fak. f¨ur Mathematik und Physik, Universit¨at Bayreuth, 95440 Bayreuth, Germany; Fak. f¨ur Informatik, Technische Universit¨at Chemnitz, 09107 Chemnitz, Germany.
  • rauber@uni-bayreuth.de
  • Received Sept 20 2001, Revised May 29 2002, Accepted March 14 2003
• C684: The Effect of Cache Models on Iterative Compilation for Combined Tiling and Unrolling
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • P.M.W. Knijnenburg, T. Kisuki, K. Gallivan and M.F.P. O'Boyle
  • LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, the Netherlands peterk@liacs.nl Phone: +31 71 5277063 Fax: +31 71 5276985; Department of Computer Science, Florida State University; Institute for Computing Systems Architecture, Edinburgh University
  • peterk@liacs.nl
  • Received Sept 20 2001, Revised May 29 2002, Accepted March 14 2003
• C685: SWARP: A Retargetable Preprocessor for Multimedia Instructions
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • Gilles Pokam, Stephane Bihan, Julien Simonnet, Francois Bodin
  • IRISA, Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France
  • gpokam@irisa.fr
  • Received Sept 20 2001, Revised May 29 2002, Accepted March 14 2003
• C686: Space-Time Mapping and Tiling – a Helpful Combination
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • Martin Griebl, Peter Faber, Christian Lengauer
  • Fakultat fur Mathematik und Informatik, Universit¨at Passau D-94030, Passau, Germany
  • griebl@fmi.uni-passau.de
  • Received Sept 20 2001, Revised May 29 2002, Accepted March 14 2003
• C687: Data Partitioning-Based Parallel Irregular Reductions
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • Eladio Gutierrez, Oscar Plata, Emilio L. Zapata
  • Department of Computer Architecture, University of Malaga E-29071, Malaga, Spain
  • eladio@ac.uma.es
  • Received Sept 20 2001, Revised May 29 2002, Accepted March 14 2003
• C688: A Fast and Accurate Method for Evaluating the Upper-Bound of Memory Performance
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • G. Fursin. M.F.P. O'Boyle, O. Temam, G. Watts
  • ICSA Division of Informatics, University of Edinburgh JCMB, King's Buildings Mayfield Rd, Edinburgh EH9 3JZ, UK; Paris South University, France
  • fgg@dcs.ed.ac.uk
  • Received Sept 20 2001, Revised May 29 2002, Accepted March 14 2003
• C689: Managing distributed shared arrays in a bulk-synchronous parallel programming environment
  • One of ten papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • Christoph W. Kessler
  • Programming Environments Laboratory (PELAB), Department of Computer Science, Linkoping University, S-581 83 Linkoping, Sweden
  • chrke@ida.liu.se
  • Received Sept 20 2001, Revised May 29 2002, Accepted July 1st 2002
• C690: Introduction to Parallel Computer Compiler Special Issue
  • Editorial for papers in Special Edition of Concurrency: Practice and Experience dedicated to selected papers presented at the ninth Compilers for Parallel Computers workshop held in Edinburgh, UK in June, 2001 (CPC 2001).
  • Michael O'Boyle
  • ICSA Division of Informatics, University of Edinburgh JCMB, King's Buildings Mayfield Rd, Edinburgh EH9 3JZ, UK
  • mob@inf.ed.ac.uk
  • Received March 14 2003, Accepted March 14 2003
• C691: A Static Mapping Heuristic for Mapping Parallel Applications to Heterogeneous Computing Systems
  • Abstract: To minimize the execution time of a parallel application running on a heterogeneous computing distributed system, an appropriate mapping scheme to allocate the application tasks to the processors is needed. The general problem of mapping tasks to machines is a well known NP-hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph-based mapping algorithm, called Heterogeneous Multi-phase Mapping ($HMM$), that permits a suboptimal mapping of a parallel application onto a heterogeneous computing distributed system by using a local search technique together with a tabu search meta-heuristic. $HMM$ allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application. We compare HMM with three different leading techniques and with an exhaustive mapping algorithm. We also give an example of mapping of a pratical application where HMM verified its usefulness. Experimental results show that $HMM$ performs well demonstrating the applicability of our approach.
  • Ranieri Baraglia, Renato Ferrini, Pierluigi Ritrovato
  • Istituto di Scienza e Tecnologie dell'Informazione A. Faedo, Consiglio Nazionale delle Ricerche Area della Ricerca di Pisa Via Moruzzi 1 56126 Pisa, Italy; Centro di Ricerca in Matematica Pura ed Applicata, Università degli Studi di Salerno Ponte Don Melillo 84084 Fisciano (Salerno), Italy.
  • ranieri.baraglia@cnuce.cnr.it
  • Received March 24 2003, Comments to Authors Oct 7 2003, Accepted March 17 2004
• C692: Concurrent Urban-Legends
  • Abstract: This discussion addresses a number of urban legends about concurrency in an attempt to separate the myth from the fact. To dispel certain legends, we argue that:
    • Concurrent != Parallel
    • Coroutining != Concurrency
    • Synchronization != Mutual Exclusion
    • Dekker !< Peterson
    • Concurrency != Library
    • Inheritance Anomaly != Major Concurrency Problem
    • Signalling != Hints
    • Spurious Wakeup != Efficiency
    • Hyman != Peer-Review Failure
    Identifying and understanding the fundamental concepts underlying concurrency is essential to the field. Equally important is not to confuse sequential and concurrent concepts. Finally, approaches based solely on efficiency are insufficient to justify a weak or difficult to use concurrent concept or construct.
  • Peter A. Buhr and Ashif S. Harji
  • University of Waterloo 200 University Ave. West Waterloo, Ontario, CANADA, N2L 3G1
  • pabuhr@plg2.math.uwaterloo.ca
  • Received March 24 2003, Comments to Authors Oct 7 2003, Accepted March 9 2004
• C693: A Cache-Efficient Implementation of the Lattice Boltzmann Method for the Two-Dimensional Diffusion Equation
  • Abstract:The lattice Boltzmann method is an important technique for the numerical solution of partial differential equations because it has nearly ideal scalability on parallel computers for many applications. However, to achieve the scalability and speed potential of the lattice Boltzmann technique, the issues of data reusability in cache-based computer architectures must be addressed. Utilizing the two-dimensional diffusion equation, T_t = µ (T_xx + T_yy), this paper examines cache optimization for the lattice Boltzmann method in both serial and parallel implementations. In this study speedups due to cache optimization were found to be 1.9 to 2.5 for the serial implementation and 3.6 to 3.8 for the parallel case in which the domain decomposition was optimized for stride-one access. In the parallel non-cached implementation the method of domain decomposition (horizontal or vertical) used for parallelization did not significantly affect the compute time. In contrast the cache-based implementation of the lattice Boltzmann method was significantly faster when the domain decomposition was optimized for stride-one access. Additionally, the cache-optimized lattice Boltzmann method in which the domain decomposition was optimized for stride-one access displayed superlinear scalability on all problem sizes as the number of processors was increased.
  • A. C. Velivelli and K. M. Bryden
  • Department of Mechanical Engineering Iowa State University, Ames, IA 50011
  • kmbryden@iastate.edu
  • Received March 29 2003, Comments to Authors Oct 8 2003, Accepted November 16 2003
• C694: Finding stale-value errors in concurrent programs
  • Abstract:Concurrent programs can suffer from many types of errors, not just the well-studied problems of deadlocks and simple race conditions on variables. This paper addresses a kind of race condition that arises from reading a variable whose value is possibly out-of-date. The paper introduces a simple technique for detecting such stale values, and reports on the encouraging experience with a compile-time checker that uses the technique.
  • Michael Burrows and K. Rustan M. Leino
  • Compaq Systems Research Center (Currently Microsoft Research)
  • leino@microsoft.com
  • Received May 1 2003, Comments to Authors Oct 8 2003, Accepted November 13 2003
• C695: XWPVM: A New Graphical Interface for PVM on Microsoft Windows Platform
  • Abstract: The present article proposes the XWPVM --- a new graphical interface for PVM implemented on Microsoft Windows platform. XWPVM assists the user in developing distributed parallel applications. The article approaches PVM, XPVM, describes the new XWPVM model, its implementation, results, and presents some conclusions.
  • Carlos B. Rosa Junior, Otávio A. S. Carpinteiro, Antonio C. Zambroni de Souza
  • Instituto de Engenharia Elétrica Universidade Federal de Itajubá Av. BPS 1303, Itajubá, MG, 37500-903, Brazil
  • otavio@iee.efei.br
  • Received May 20 2003, Comments to Authors Oct 8 2003
• C696: The J2EE ECperf Benchmark Results: Transient Trophies or Technology Treasures?
  • Abstract: ECperf, the widely recognized industry standard J2EE benchmark, has attracted a large number of results submissions and their subsequent publication. However, ECperf places little restriction on the hardware platform, operating systems and databases utilized in the benchmarking process. This, combined with the existence of only two primary metrics, makes it difficult to accurately compare the performance of the Application Server products themselves. By mining the full-disclosure archives for trends and correlations we have discovered that J2EE technology is very scalable both in a scale-up and scale-out manner. Other observed trends include, a linear correlation between middle-tier total processing power and throughput, as well as between J2EE Application Server license costs and throughput. However, the results clearly indicate that there is an increasing cost per user with increasing capacity systems, and scale-up is proportionately more expensive than scale-out. Finally, the correlation between middle-tier processing power and throughput, combined with results obtained from a different 'lighter-weight' benchmark, facilitates an estimate of throughput for different types of J2EE applications.
  • Paul Brebner, Jeffrey Gosper
  • CSIRO Mathematical and Information Sciences, GPO Box 664, Canberra, AUSTRALIA
  • Paul.Brebner@csiro.au
  • Received May 21 2003; Accepted July 21 2003
• C697: PIPELINES ON HETEROGENEOUS SYSTEMS: MODELS AND TOOLS
  • Abstract: We study the performance of pipeline algorithms in heterogeneous networks. The concept of heterogeneity is not restricted only to the differences in computational power of the nodes but also refers to the network capabilities. We develop an skeleton tool that allows an efficient block-cyclic mapping of pipelines on heterogeneous systems. The tool supports pipelines with a number of stages much larger than the number of physical processors available. We derive an analytical formula that allows to predict the performance of pipelines in heterogeneous systems. According to the analytical complexity formula, numerical strategies to solve the optimal mapping problem are proposed. The computational results prove the accuracy of the predictions and effectiveness of the approach
  • Francisco Almeida, Luz Marina Moreno, Daniel González and Casiano Rodríguez
  • Dpto. Estadística, I. O. y Computación Edificio Físicas/Matemáticas, Universidad de La Laguna La Laguna, Tenerife Spain
  • falmeida@ull.es
  • Received May 29 2003, Comments to Authors Oct 8 2003, Accepted March 9 2004
• C698: Autonomic Oil Reservoir Optimization on the Grid
  • Abstract:The emerging Grid infrastructure and its support for seamless and secure interactions is enabling a new generation of autonomic applications where the application components, Grid services, resources, and data interact as peers to manage, adapt and optimize themselves and the overall application. In this paper we describe the design, development and operation of a prototype of such an application that uses peer-to-peer interactions between distributed services and data on the Grid to enable the autonomic optimization of an oil reservoir.
  • Viraj Bhat, Vincent Matossian, Manish Parashar, Magorzata Peszynska, Mrinal Sen, Paul Stoffa and Mary F. Wheeler
  • The Applied Software Systems Laboratory, Rutgers University, Piscataway, NJ.; Center for Subsurface Modeling, University of Texas at Austin, Austin, TX.; Institute for Geophysics, University of Texas at Austin, Austin, TX.
  • parashar@caip.rutgers.edu
  • Received June 14 2003, Comments to Authors Oct 8 2003, Accepted December 6 2003
• C699: Loosely Coordinated Coscheduling in the Context of Other Approaches for Dynamic Job Scheduling: A Survey
  • Abstract: Loosely coordinated (implicit/dynamic) coscheduling is a time-sharing approach which originates from NOW environments of mixed parallel/sequential workloads and limited software support. It is meant to be an easy-to-implement and scalable approach. Considering that the percentage of clusters in parallel computing is increasing and easily portable software is needed, loosely-coordinated coscheduling becomes an attractive approach for dedicated machines, too. Loose coordination offers attractive features as a dynamic approach. Static approaches for local job scheduling assign resources exclusively and nonpreemptively. Such approaches still remain beyond the desirable resource utilization and average response times. Conversely, approaches for dynamic scheduling of jobs can preempt resources and/or adapt their allocation. They typically provide better resource utilization and response times. Existing dynamic approaches are full preemption with checkpointing, dynamic adaptation of CPU allocation, and time sharing via gang or loosely coordinated coscheduling. This survey presents and compares the different approaches, while focussing especially on the less well explored loosely coordinated time sharing. The discussion focuses especially on the implementation problems, in terms of modification of standard operating systems, the runtime system and the communication libraries.
  • Angela C. Sodan
  • University of Windsor, Computer Science, 401 Sunset Ave., Windsor, ON N9B 3P4 Canada
  • acsodan@davinci.newcs.uwindsor.ca
  • Received June 12 2003, Comments to Authors Oct 10 2003, Accepted March 9 2004
• C700: Scheduling Communication in Multithreaded Programs: Experimental Results
  • Abstract: when the critical path of a communication session between end-points includes the actions of operating system kernels, there are attendant overheads. Along with other factors, such as functionality and flexibility, such overheads motivate and favor the implementation of communication protocols in user-space. When implemented with threads, such protocols may hold the key to optimal communication performance and functionality. Based on implementations of reliable user-space protocols supported by a threads framework, we focus on our experiences with internal threads' scheduling techniques and their potential impact on performance. We present scheduling strategies that enable threads to do both application-level and communication-related processing. With experiments performed on a Sun SPARC-5 LAN environment, we show how different scheduling strategies yield different levels of application-processing efficiency, communication latency and packet-loss. This work forms part of a larger study on the implementation of multiple threads-based protocols in a single address-space, and the benefits of coupling protocols with applications.
  • Juan Carlos Gomez, Vernan Rego and V.S. Sunderam
  • Department of Computer Sciences, Purdue University, West Lafayette, IN 47907; Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322
  • rego@cs.purdue.edu
  • Received June 16 2003, Comments to Authors Oct 10 2003, Accepted April 12 2004
• C731: Fixed Memory Performance Of A 3-D Electromagnetic PIC Model
  • Abstract:Using a parallel 3 dimensional fully kinetic electromagnetic particle-in-cell (PIC) model, the fixed memory performance was examined thoroughly on the SGI-Origin 2000 supercomputer with 128 processors. This parallel PIC model is decomposed only in one dimension with fixed domain size in each processor. The detailed computational and communication overhead times incurred by each of the members such as the density solver, the Maxwell solver and the particle pusher, constituting our PIC model is presented here. This type of performance analysis is very important in understanding and improving the overall efficiency of the model.
  • Saikat Saha
  • Department of Electrical and Computer Engineering, The University of Alabama in Huntsville, Huntsville, AL-35899, USA.
  • saikat_saha@hotmail.com
  • Received June 2 2003, Comments to Authors Oct 10 2003
• C732: The Performance and Scalability of SHMEM and MPI-2 One-Sided Routines on a SGI Origin 2000 and a Cray T3E-600
  • Abstract: This paper compares the performance and scalability of SHMEM and MPI-2 one-sided routines on different communication patterns for a SGI Origin 2000 and a Cray T3E-600. The communication tests were chosen to represent commonly-used communication patterns with low contention (accessing distant messages, a circular right shift, a binary tree broadcast) to communication patterns with high contention (a "naive" broadcast and an all-to-all). For all the tests and for small message sizes, the SHMEM implementation significantly outperformed the MPI-2 implementation for both the SGI Origin 2000 and the Cray T3E-600.
  • Glenn R. Luecke, Silvia Spanoyannis, Marina Kraeva
  • Iowa State University Ames, Iowa 50011-2251 USA
  • grl@iastate.edu
  • Performance Section: Received November 20 2001, Revised September 10 2002, Accepted December 13 2002
• C733: Semantic Resource Grid: Model, Method and Platform
  • Abstract: This paper proposes the Semantic Resource Grid model, which aims at effectively sharing using and managing versatile resources across the Internet. The kernel of the Resource Grid includes a resource space model RSM and a uniform resource-using mechanism RUM. The RSM is a coordinate system with independent coordinates and orthogonal axes for uniformly specifying resources. A resouirce space has three schemas: a user-view schema that enables users to easily operate and intelligently use resources, a universal-resource-view schema for uniformly managing globally distributed resources, and a semantic-web-view schema that provides across-platform and machine-understandable resource representation. The RUM provides not only the end-users with an operable resource browser to operate resources in the user-view schema by using the built-in Resource Operation Language ROL but also the application developers with the ROL-based programming environment. The criteria and method for guiding designers to design a proper resource space are presented. A software platform based on the proposed model has been implemented and used for resource sharing and management in distributed research teams.
  • Hai Zhuge
  • Knowledge Grid Research Group, Key Lab of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, 100080, P.R. China
  • zhuge@ict.ac.cn
  • Received June 4 2003, Comments to Author Oct 10 2003, Accepted November 13 2003
• C734: An Analytical Study of MPI Middleware Architecture and its Impact on Performance
  • Abstract:This paper presents an analytical study on MPI middleware architecture for the MPI-1.2 standard, major distinguishing characteristics of MPI implementations and their impacts on parallel application performance. The model used to characterize parallel performance is reviewed and metrics complementing this model and useful for describing messgae-passing performance are introduced. They capture key aspects of application performance and are practically measurable.
    The key contribution of this paper is a demonstration that the architecture of the MPI library has a strong impact on its ability to deliver application performance, and that pollling architectures (typical of early and still commonly used MPI implementations) are suboptimal in terms of parallel application runtime. A classification taxonomy for MPI-1 libraries is offered, and existing libraries are so classified.
    This paper offers comparisons of blocking and polling modes of the MPI/Pro implementation of MPI, offering a direct comparison of these strategies for implementing MPI. A complementary direct comparison of MPI/Pro and MPICH performance is also offered to show the net benefits of blocking MPI implementation on ceratin real applications' performance.
    This paper demonstrates the need for performance analysis of MPI libraries to go beyond micro-benchmarking of zero-message-length latency and asymptotic message bandwidth in order to grade the "quality" of an MPI implementation.
  • Rossen Dimitrov and Anthony Skjellum
  • Dept. of Computer and Information Sciences, University of Alabama at Birmingham, High Performance Computing Laboratory, 1300 University Blvd., 115A Campbell Hall, Birmingham AL 39294-1170
  • tony@MPI-SoftTech.Com
  • Received July 2 2003, Comments to Authors Oct 10 2003
• C735: Semantic Link Network Builder and Intelligent Semantic Browser
  • Abstract:Semantic Link Network SLN is a semantic web model using semantic links to replace the hyperlinks of the current Web. Semantic Link Network Builder SLN-Builder is a software tool that enables definition, modification, verification and access of SLN. The SLN-Builder can convert an SLN definition into XML descriptions for cross-platform information exchange. The Intelligent Semantic Browser can browse SLN and carry out two types of reasoning: small granularity reasoning by chaining semantic links and large granularity reasoning by matching semantic views of SLN. With the help of reasoning mechanism, the browser can recommend the content that is semantically relevant to the current browsing content and enables the user to foresee the end-side content of a semantic link chain. This paper presents the design and implementation of the SLN-Builder and the intelligent browser as well as the key algorithms.
  • Hai Zhuge and Ruixiang Jia
  • Knowledge Grid Research Group, Key Lab of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, 100080, P.R. China
  • zhuge@ict.ac.cn
  • Received 18 July 2003, Comments to Authors Oct 10 2003, Accepted November 16 2003
• C736: Augmenting LZ-77 with authentication and integrity assurance capabilities
  • Abstract: The formidable dissemination capability allowed by the current network technology makes it increasingly important to devise new methods to ensure authenticity and integrity. Nowadays it is common practice to distribute documents in compressed form. In this paper, we propose a simple variation on the classic LZ-77 algorithm that allows one to hide, within the compressed document, enough information to warrant its authenticity and integrity. The design is based on the unpredictability of a certain class of pseudo- random number generators, in such a way that the hidden data cannot be retrieved in a reasonable amount of time by an attacker (unless the secret bit-string key is known). Since it can still be decompressed by the original LZ-77 algorithm, the embedding is completely \transparent" and backward-compatible, making it possible to deploy it without disrupting service. Experiments show that the degradation in compression due to the embedding is almost negligible.
  • Special Issue of SAC'03 Security Track edited by Ronaldo Menezes
  • Mikhail J. Atallah, Stefano Lonardi
  • CERIAS and Department of Computer Sciences, Purdue University, West Lafayette, IN 47907, USA.; Department of Computer Science and Engineering, University of California, Riverside, CA 92521, USA.
  • stelo@cs.ucr.edu
  • Received 27 June 2003, Accepted August 23 2003
• C737: Identification and Authentication of Integrated Circuits
  • Abstract:This paper describes a technique to reliably and securely identify individual integrated circuits (ICs) based on the precise measurement of circuit delays and a simple challenge- response protocol. This technique could be used to produce key-cards that are more difficult to clone than ones involving digital keys on the IC. We consider potential venues of attack against our system, and present candidate implementations. Experiments on Field Programmable Gate Arrays show that the technique is viable, but that our current implementations could require some strengthening before it can be considered as secure.
  • Special Issue of SAC'03 Security Track edited by Ronaldo Menezes
  • Blaise Gassend, Daihyun Lim, Dwaine Clarke, Marten van Dijk, Srinivas Devadas
  • Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA 02139, USA; Prof Holstlaan 4, Eindhoven, The Netherlands
  • blaise@gassend.com
  • Received 27 June 2003, Accepted August 23 2003
• C738: Access-Controlled Resource Discovery in Pervasive Networks
  • Abstract:Networks of the future will be characterized by a variety of computational devices that display a level of dynamism not seen in traditional wired networks. Because of the dynamic nature of these networks, resource discovery is one of the fundamental problems that must be solved. While resource discovery systems are not a novel concept, securing these systems in an efficient and scalable way is challenging. This paper describes the design and implementation of an architecture for access-controlled resource discovery. This system achieves this goal by integrating access control with the Intentional Naming System (INS), a resource discovery and service location system. The integration is scalable, efficient, and ts well within a proxy-based security framework designed for dynamic networks. We provide performance experiments that show how our solution outperforms existing schemes. The result is a system that provides secure, access- controlled resource discovery that can scale to large numbers of resources and users.
  • Special Issue of SAC'03 Security Track edited by Ronaldo Menezes
  • Sanjay Raman, Dwaine Clarke, Matt Burnside, Srinivas Devadas, Ronald Rivest
  • Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA 02139, USA
  • sraman@abp.lcs.mit.edu
  • Received 27 June 2003, Accepted August 23 2003
• C739: A role-based infrastructure management system: design and implementation
  • Abstract: Over the last decade there has been tremendous advance in the theory and practice of role-based access control (RBAC). One of the most significant aspects of RBAC can be viewed from its management of permissions on the basis of roles rather than individual users. Consequently, it reduces administrative costs and potential errors. The management of roles in various RBAC implementations, however, tends to be conducted in an ad-hoc basis, closely coupled with a certain context of system environments. This paper discusses the development of a system whose purpose is to help manage a valid set of roles with assigned users and permissions for role-based authorization infrastructures. We have designed and implemented the system, called RolePartner. The system enables role administrators to build and configure various components of a RBAC model so as to embody organizational access control policies which can be separated from di®erent enforcement mechanisms. Hence the system helps make it possible to lay a foundation for role-based authorization infrastructures. Three methodological constituents for our purpose are introduced, together with the design and implementation issues. The system has a role-centric view for easily managing constrained and hierarchical roles as well as assigned users and permissions. An LDAP-accessible directory service was used for a role database. We show that the system can be seamlessly integrated with an existing privilege-based authorization infrastructure.
  • Special Issue of SAC'03 Security Track edited by Ronaldo Menezes
  • Dongwan Shin, Gail-Joon Ahn, Sangrae Cho, and Seunghun Jin
  • The University of North Carolina at Charlotte; Electronics and Telecommunications Research Institute
  • doshin@uncc.edu
  • Received 27 June 2003, Accepted August 23 2003
• C740: Editorial for Special Issue of SAC'03 Security Track
  • Abstract: Editorial for Special Issue of SAC'03 Security Track
  • Special Issue of SAC'03 Security Track edited by Ronaldo Menezes
  • rmenezes@cs.fit.edu
  • Florida Institute of Technology, Department of Computer Sciences, 150 West University Blvd., Melbourne, FL 32901
  • rmenezes@cs.fit.edu
  • Accepted August 14 2003
• C741: Simple verification techniques for complex Java bytecode subroutines
  • Abstract:Java is normally compiled to bytecode, which is verified and then executed by the Java Virtual Machine. Bytecode produced via compilation must pass verification. The main cause of complexity for bytecode verification is subroutines, used by compilers to generate more compact code. The techniques to verify subroutines proposed in the literature reject certain programs produced by mundane compilers, are difficult to realize within an implementation of the Java Virtual Machine, or are relatively complicated. This paper presents a novel technique which is very simple to understand, implement, and prove sound. It is also very powerful: the set of accepted programs has a simple characterization which most likely includes all code produced by current compilers and which enables future compilers to make more extensive use of subroutines.
  • Special Issue for Formal Techniques for Java-like Programs workshop at ECOOP.2002Málaga, Spain, June 10, 2002 edited by Peter Mueller, David Naumann and Erik Poll
  • Alessandro Coglio
  • Kestrel Institute, 3260 Hillview Avenue, Palo Alto, CA 94304, USA
  • coglio@kestrel.edu
  • Received January 5 2003, Revised May 9 2003, Accepted July 25 2003
• C742: Checking Ownership and Confinement
  • Abstract:A number of proposals to manage aliasing in Java-like programming languages have been advanced over the last five years. It is not clear how practical these proposals are, that is, how well they relate to the kinds of programs currently written in Java-like languages. To address this problem, we analysed heap snapshots from a corpus of Java programs. Our results indicate that object-oriented programs do in fact exhibit symptoms of encapsulation in practice, and that proposed models of uniqueness, ownership, and confinement can usefully describe the aliasing structures of object-oriented programs. Understanding the kinds of aliasing present in programs should help us to design formalisms to make explicit the kinds of aliasing implicit in object-oriented programs.
  • Special Issue for Formal Techniques for Java-like Programs workshop at ECOOP.2002 Málaga, Spain, June 10, 2002 edited by Peter Mueller, David Naumann and Erik Poll
  • Alex Potanin, James Noble, and Robert Biddle
  • School of Mathematical and Computing Sciences, Victoria University of Wellington, PO Box 600, Wellington, New Zealand
  • kjx@mcs.vuw.ac.nz
  • Received January 5 2003, Revised May 9 2003, Accepted July 25 2003
• C743: Analysing the Java Package/Access Concepts in Isabelle/HOL
  • Abstract: Java access modifiers and packages provide a mechanism to restrict access to members and types, as an additional means of information hiding beyond the purely object-oriented concept of classes. In this paper we clarify the semantics of access modifiers and packages by adding them to our formal model of Java in the theorem prover Isabelle/HOL. We analyse which properties we can rely on at runtime, provided that the program has passed the static accessibility tests.
  • Special Issue for Formal Techniques for Java-like Programs workshop at ECOOP.2002 Málaga, Spain, June 10, 2002 edited by Peter Mueller, David Naumann and Erik Poll
  • Norbert Schirmer
  • Technische Universitaet Muenchen, Department of Informatics, D-85748 Garching, Germany
  • schirmer@in.tum.de
  • Received January 5 2003, Revised May 9 2003, Accepted July 25 2003
• C744: Transposing F to C#: Expressivity of parametric polymorphism in an object-oriented language
  • Abstract: We present a type-preserving translation of System F (the polymorphic lambda calculus) into a forthcoming revision of the C# programming language supporting parameterized classes and polymorphic methods. The forthcoming revision of Java in JDK 1.5 also makes a suitable target. We formalize the translation using a subset of C# similar to Featherweight Java. We prove that the translation is fully type-preserving and that it preserves behaviour via the novel use of an environment-style semantics for System F. We observe that whilst parameterized classes alone are sufficient to encode the parameterized datatypes and let-polymorphism of languages such as ML and Haskell, it is the presence of dynamic dispatch for polymorphic methods that supports the encoding of the "first-class polymorphism" found in System F and recent extensions to ML and Haskell.
  • Special Issue for Formal Techniques for Java-like Programs workshop at ECOOP.2002 Málaga, Spain, June 10, 2002 edited by Peter Mueller, David Naumann and Erik Poll
  • Andrew Kennedy and Don Syme
  • Microsoft Research, Cambridge, U.K., 7 J J Thomson Ave, Cambridge CB3 0FB, UK
  • akenn@microsoft.com
  • Received January 5 2003, Revised May 9 2003, Accepted July 25 2003
• C745: Special Issue: Formal Techniques for Java-like Language
  • Abstract:Overview of Formal Techniques for Java-like Language Special Issue
  • Special Issue for Formal Techniques for Java-like Programs workshop at ECOOP.2002 Málaga, Spain, June 10, 2002 edited by Peter Mueller, David Naumann and Erik Poll
  • Peter Müller, David A. Naumann, Erik Poll
  • Computing Science Institute University of Nijmegen
  • erikpoll@cs.kun.nl
  • Received July 16 2003, Accepted July 25 2003
• C746: A Parallel Update Algorithm for Concurrency Control in Data Warehousing Systems
  • Abstract:To speed up on-line analytical processing, data warehouse, which is usually derived from operational databases, is introduced. When the operational databases happen to change, the data warehouse gets stale. To maintain the freshness of data warehouse, such changes need to be frequently and concurrently propagated into the data warehouse. However, if several update transactions are allowed to execute concurrently without an appropriate concurrency control, data inconsistency between data warehouse and operational databases could arise due to incorrect propagation of the updates on the operational databases into the data warehouse. In this paper, we propose a concurrency control algorithm, which could concurrently execute a number of update transactions in a consistent way. To investigate the applicable areas of our algorithm, its performance is evaluated by means of simulation approach. Our experimental results show that the proposed algorithm enables analytical transactions to read fresher data than other representative concurrency control algorithms.
  • Jinbae Kim
  • Department of Computer Science, Anyang Technical College, Republic of Korea
  • jbkim@ianyang.ac.kr
  • Received August 28 2002, Comments to Author July 24 2003
• C747: Simulation of Resource Synchronization in a Dynamic Real-Time Distributed Computing Environment
  • Abstract:Today, more and more distributed computer applications are being modeled and constructed using real-time principles and concepts. In 1989, the Object Management Group (OMG) formed a Real-Time Special Interest Group (RT SIG) with the goal of extending the Common Object Request Broker Architecture (CORBA) standard to include real-time specifications. This group’s most recent efforts have focused on the requirements of dynamic distributed real-time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that the authors have developed which meet the requirements of dynamic distributed realtime systems as specified by Dynamic Scheduling Real-Time CORBA (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. In order to evaluate the performance of the proposed protocols, we analyzed each protocol’s schedulability. Since the schedulability of the system is affected by numerous system configuration parameters, we have designed simulation experiments to isolate and illustrate the impact of each individual system parameter. Simulation experiments show the proposed protocols have better performance than one would realize by applying a schema that utilizes dynamic priority ceiling update.
  • Chen Zhang, David Cordes
  • Dept. of Computer Information Systems Bryant College Smithfield, RI 02917-1284; Department of Computer Science The University of Alabama Tuscaloosa, AL 35487-0290
  • czhang@bryant.edu
  • Received July 14 2003, Comments to Authors Oct 12 2003, Accepted Nov 16 2003
• C748: Evaluation of Cache-based Superscalar and Cacheless Vector Architectures for Scientific Computations
  • Abstract: The growing gap between sustained and peak performance for scientific applications is a well-known problem in high end computing. The recent development of parallel vector systems offers the potential to bridge this gap for many computational science codes and deliver a substantial increase in computing capabilities. This paper examines the intranode performance of the NEC SX-6 vector processor and the cache-based IBM Power3/4 superscalar architectures across a number of scientific computing areas. First, we present the performance of a microbenchmark suite that examines low-level machine characteristics. Next, we study the behavior of the NAS Parallel Benchmarks. Finally, we evaluate the performance of several scientific computing codes. Results demonstrate that the SX-6 achieves high performance on a large fraction of our applications and often significantly outperforms the cache-based architectures. However, certain applications are not easily amenable to vectorization and would require extensive algorithm and implementation reengineering to utilize the SX-6 effectively.
  • Leonid Oliker, Andrew Canning, Jonathan Carter, John Shalf, David Skinner, Stephane Ethier, Rupak Biswas, Jahed Djomehri, and Rob Van der Wijngaart
  • CRD/NERSC, Lawrence Berkeley National Laboratory, Berkeley, CA 94720; Princeton Plasma Physics Laboratory, Princeton University, Princeton, NJ 08453; NAS Division, NASA Ames Research Center, Moffett Field, CA 94035
  • rbiswas@nas.nasa.gov
  • Received August 15 2003, Comments to Authors December 30 2003, Accepted March 9 2004
• C776: Composition and On Demand Deployment of Distributed Brain Activity Analysis Application on Global Grids
  • Abstract:The distribution of knowledge (by scientists) and data sources (advanced scientific instruments), and the need of large-scale computational resources for analyzing massive scientific data are two major problems commonly observed in scientific disciplines. The two popular scientific disciplines of this nature are brain science and high-energy physics. The analysis of brain activity data gathered from the MEG (Magnetoencephalography) instrument is an important research topic in medical science since it helps doctors in identifying symptoms of diseases. The data needs to be analyzed exhaustively to efficiently diagnose and analyze brain functions and requires access to large-scale computational resources. The potential platform for solving such resource intensive applications is the Grid. This paper presents the design and development of MEG data analysis system by leveraging Grid technologies, primarily Nimrod-G, Gridbus, and Globus. It describes the composition of the neuroscience (brain activity analysis) application as parameter-sweep application and its on-demand deployment on Global Grids for distributed execution.
  • R. Buyya, S. Date, Y. Mizuno-Matsumoto, S. Venugopal, and D. Abramson
  • Grid Computing and Distributed Systems (GRIDS) Laboratory, Dept. of Computer Science and Software Engineering, University of Melbourne, Australia; Graduate School of Information Science and Technology, Department of Bioinformatic Engineering, Osaka University, Japan; Department of Information Systems Engineering, Graduate School of Osaka University, Japan; School of Computer Science and Software Engineering, Monash University, Australia
  • raj@cs.mu.oz.au
  • Received September 10 2003, Comments to Authors December 30, 2003, Accepted March 9 2004
• C777: Distributed Computing with Triana on the Grid
  • Abstract:In this paper, we describe Triana, a distributed problem-solving environment that makes use of the Grid to enable a user to compose applications from a set of components, select resources on which the composed application can be distributed and then execute the application on those resources. We describe Triana’s current pluggable architecture that can support many different modes of operation by the use of flexible writers for many popular web service choreography languages. We further show, that the Triana architecture is middleware independent through the use of the Grid Application Toolkit (GAT) API and demonstrate this through the use of a GAT binding to JXTA. We describe how other bindings being developed to Grid infrastructures, such as OGSA, can seamlessly be integrated within the current prototype by using the switching capability of the GAT. Finally, we outline an experiment we conducted using this prototype and discuss its current status.
  • Dr Ian Taylor, Dr Ian Wang , Matthew Shields, Shalil Majithia
  • School of Computer Science, Cardiff University
  • shalil.majithia@cs.cardiff.ac.uk
  • Received September 10 2003, Comments to Authors December 31 2003, Accepted March 15 2004
• C778: Parallel Gain-Bandwidth Characteristics Calculations for Thin Avalanche Photodiodes on an SGI Origin 2000 Supercomputer
  • Abstract:An important factor for high speed optical communication is the availability of ultrafast and low-noise photodetectors. Among the semiconductor photodetectors that are commonly used in today's long-haul and metro-area fiber-optic systems, avalanche photodiodes (APDs) are often preferred over p-i-n photodiodes due to their internal gain, which significantly improves the receiver sensitivity and alleviates the need for optical pre-amplification. Unfortunately, the random nature of the very process of carrier impact ionization, which generates the gain, is inherently noisy and results in fluctuations not only in the gain but also in the time response. Recently, a theory characterizing the autocorrelation function (or the power spectral density) of APDs has been developed by us which incorporates the dead-space effect. The research extends the time-domain analysis of the dead-space multiplication model to compute the autocorrelation function of the APD impulse response. However, the computation requires a large amount of memory space and is very time consuming. In this research, we describe our experiences in parallelizing the code using in MPI and OpenMP using CAPTools. Several array partitioning schemes and scheduling policies are implemented and tested. Our results show that the code is scalable up to 64 processors on an SGI Origin 2000 machine and has small average errors.
  • Yi Pan, Constantinos S. Ierotheou, and Majeed M. Hayat
  • \Department of Computer Science Georgia State University Atlanta, GA 30303, USA; Parallel Processing Research Group University of Greenwich London SE10 9LS, UK; Majeed M. Hayat Department of Electrical & Computer Engineering The University of New Mexico Albuquerque, NM 87131-1356, USA
  • pan@cs.gsu.edu
  • Performance Section: Received 9 September 2002, Accepted 5 September 2003
• C779: Lightweight monitoring of MPI programs in real-time
  • Abstract:Current technologies allow efficient data collection by several sensors to determine the overall evaluation of the status of a cluster. However, no previous work of which we are aware analyzes the behavior of the parallel programs themselves in real-time. In this paper, we perform a comparison of different artificial intelligence techniques that can be used to implement a lightweight monitoring and analysis system for parallel applications on a cluste