Volume 21, 2002, No. 1

A Clustering Method for Modeling the Communication Requirements of Message-Passing Applications

Juan Manuel ORDUNA, Federico SILLA, José DUATO   Abstract Clusters have become a very cost-effective platform for high-performance computing. Usually these systems become heterogeneous as they grow, due to their incremental capabilities. Many research activities have focused on the problem of task scheduling in heterogeneous systems from the computational point of view. However, an ideal scheduling strategy would also take into account the communication requirements of the applications and the communication bandwidth available in the network. One of the key issues in this strategy is the measurement of the communication requirements for each application. In this paper, we propose a clustering-based method to characterize the communications between processes generated by message-passing applications. This technique provides a model consisting of several partitions of the processes generated by the application. Also, we propose a criterion to measure the quality of the obtained partitions. This approach can be used when a given application is repeatedly executed with different input data. Results show that the proposed method can provide a partition with the highest ratio between the intracluster and the intercluster required communication bandwidth. This partition can be used to map groups of processes to processors in the heterogeneous system.

 

A User Modeling Approach for Server Request Prediction

Ernst-Georg HAFFNER   Abstract This article describes a model to perform user request prediction for remote data servers. It is useful to improve the user perceived latency of client requests. In this contribution, not only the mathematical formulas for the prediction theory are derived, but also the methodological approach to model adequate user behavior. The evaluation results of the provided prediction model are very promising and allow also reversed engineering: user request behavior can thus be classified.

 

Parallel Priority Queue and List Contraction: The BSP Approach

Alexandros V. GERBESSIOTIS, Constantinos J. SINIOLAKIS, Alexandre TISKIN   Abstract In this work we present efficient and practical randomized data structures on the Bulk-Synchronous Parallel (BSP) model of computation along with an experimental study of their performance. In particular, we study data structures for the realization of Parallel Priority Queues (PPQs). We show that our algorithms are communication efficient and achieve optimality to within small multiplicative constant factors for a wide range of parallel machines. We also present an experimental study of our PPQ algorithms on a Cray T3D\@. Finally, we present new randomized and deterministic BSP algorithms for list and tree contraction.

 

Learning Spatial Relations Using an Inductive Logic Programming System

Maria do Carmo NICOLETTI, Jane BRENNAN   Abstract The ability to learn spatial relations is a prerequisite for performing many relevant tasks such as those associated with motion, orientation, navigation, etc. This paper reports on using an Inductive Logic Programmming (ILP) system for learning function-free Horn-clause descriptions of spatial knowledge. Its main contribution, however, is to show that an existing relation between two reference systems --- the speaker-relative and the absolute --- can be automatically learned by an ILP system, given the proper background knowledge and positive examples.

 

Volume 21, 2002, No. 1