IFIP TC6 Open Digital Library

12. Euro-Par 2006: Dresden, Germany

Euro-Par 2006, Parallel Processing, 12th International Euro-Par Conference, Dresden, Germany, August 28 - September 1, 2006, Proceedings

Wolfgang E. Nagel, Wolfgang V. Walter, Wolfgang Lehner

Springer, Lecture Notes in Computer Science 4128, ISBN: 3-540-37783-2



Contents

Support Tools and Environments

Topic 1: Support Tools and Environments.

Bronis R. de Supinski, Matthias Brehm, Luiz De Rose, Tomàs Margalef

 1

IOAgent: A Parallel I/O Workload Generator.

Sergio Gómez-Villamor, Victor Muntés-Mulero, Marta Pérez-Casany, John Tran, Steve Rees, Josep-Lluis Larriba-Pey

 3-14

TDP_SHELL: An Interoperability Framework for Resource Management Systems and Run-Time Monitoring Tools.

Vicente Ivars, Ana Cortés, Miquel A. Senar

 15-24

Supporting Cache Locality Optimization with a Toolset.

Jie Tao, Wolfgang Karl

 25-34

Model-Based Performance Diagnosis of Master-Worker Parallel Computations.

Li Li 0020, Allen D. Malony

 35-46

Specification of Inefficiency Patterns for MPI-2 One-Sided Communication.

Andrej Kühnal, Marc-André Hermanns, Bernd Mohr, Felix Wolf

 47-62

Performance Prediction and Evaluation

Topic 2: Performance Prediction and Evaluation.

Jesús Labarta, Bernd Mohr, Allan Snavely, Jeffrey S. Vetter

 63

Hierarchical Model Validation of Symbolic Performance Models of Scientific Kernels.

Sadaf R. Alam, Jeffrey S. Vetter

 65-77

Tuning Application in a Multi-cluster Environment.

Eduardo Argollo, Adriana Gaudiani, Dolores Rexachs, Emilio Luque

 78-88

Analyzing the Interaction of OpenMP Programs Within Multiprogramming Environments on a Sun Fire E25K System with PARbench.

Rick Janda, Wolfgang E. Nagel, Bernd Trenkler

 89-98

Early Experiences with KTAU on the IBM BG/L.

Aroon Nataraj, Allen D. Malony, Alan Morris, Sameer Shende

 99-110

PAM-SoC: A Toolchain for Predicting MPSoC Performance.

Ana Lucia Varbanescu, Henk J. Sips, Arjan J. C. van Gemund

 111-123

Analysis of the Memory Registration Process in the Mellanox InfiniBand Software Stack.

Frank Mietke, Robert Rex, Robert Baumgartl, Torsten Mehlan, Torsten Hoefler, Wolfgang Rehm

 124-133

Optimization of Dense Matrix Multiplication on IBM Cyclops-64: Challenges and Experiences.

Ziang Hu, Juan del Cuvillo, Weirong Zhu, Guang R. Gao

 134-144

Optimizing OpenMP Parallelized DGEMM Calls on SGI Altix 3700.

Daniel Hackenberg, Robert Schöne, Wolfgang E. Nagel, Stefan Pflüger

 145-154

Scheduling and Load Balancing

Topic 3: Scheduling and Load Balancing.

Michael Bender, Dror G. Feitelson, Allan Gottlieb, Uwe Schwiegelshohn

 155

The Price of Approximate Stability for Scheduling Selfish Tasks on Two Links.

Eric Angel, Evripidis Bampis, Fanny Pascual

 157-166

Master-Slave Tasking on Asymmetric Networks.

Cyril Banino-Rokkones, Olivier Beaumont, Lasse Natvig

 167-176

Using On-the-Fly Simulation for Estimating the Turnaround Time on Non-dedicated Clusters.

Mauricio Hanzich, Josep L. Lérida, Matías Torchinsky, Francesc Giné, Porfidio Hernández, Emilio Luque

 177-187

An Adaptive Scheduling Method for Grid Computing.

Salah-Salim Boutammine, Daniel Millot, Christian Parrot

 188-197

On the Placement of Reservations into Job Schedules.

Thomas Röblitz, Krzysztof Rzadca

 198-210

A Practical Approach of Diffusion Load Balancing Algorithms.

Emmanuel Jeannot, Flavien Vernier

 211-221

Fast Diffusion Load Balancing Algorithms on Torus Graphs.

Gregory Karagiorgos, Nikolaos M. Missirlis, Filippos Tzaferis

 222-231

A Parallel Shape Optimizing Load Balancer.

Henning Meyerhenke, Stefan Schamberger

 232-242

Improvement of the Efficiency of Genetic Algorithms for Scalable Parallel Graph Partitioning in a Multi-level Framework.

Cédric Chevalier, François Pellegrini

 243-252

Probablistic Self-Scheduling.

Milind Girkar, Arun Kejariwal, Xinmin Tian, Hideki Saito, Alexandru Nicolau, Alexander V. Veidenbaum, Constantine D. Polychronopoulos

 253-264

Data Sharing Conscious Scheduling for Multi-threaded Applications on SMP Machines.

Shlomit S. Pinter, Marcel Zalmanovici

 265-275

Compilers for High Performance

Topic 4: Compilers for High Performance.

William Jalby, Oscar G. Plata, Barbara M. Chapman, Paul Kelly

 277

Compiler Technology for Blue Gene Systems.

Stefan Kral, Markus Triska, Christoph W. Ueberhuber

 279-288

SCAN: A Heuristic for Near-Optimal Software Pipelining.

Florent Blachot, Benoît Dupont de Dinechin, Guillaume Huard

 289-298

Code Generation for STA Architecture.

Jie Guo, Torsten Limberg, Emil Matús, Björn Mennenga, Reimund Klemm, Gerhard Fettweis

 299-310

Multi-dimensional Kernel Generation for Loop Nest Software Pipelining.

Alban Douillet, Hongbo Rong, Guang R. Gao

 311-322

Towards a Versatile Pointer Analysis Framework.

Rosa Castillo, Adrian Tineo, Francisco Corbera, Angeles G. Navarro, Rafael Asenjo, Emilio L. Zapata

 323-333

Parallel and Distributed Databases, Data Mining and Knowledge Discovery

Topic 5: Parallel and Distributed Databases, Data Mining and Knowledge Discovery.

Patrick Valduriez, Wolfgang Lehner, Domenico Talia, Paul Watson

 335

Dynamic and Distributed Reconciliation in P2P-DHT Networks.

Vidal Martins, Esther Pacitti

 337-349

HyParSVM - A New Hybrid Parallel Software for Support Vector Machine Learning on SMP Clusters.

Tatjana Eitrich, Wolfgang Frings, Bruno Lang

 350-359

Supporting a Real-Time Distributed Intrusion Detection Application on GATES.

Qian Zhu, Liang Chen, Gagan Agrawal

 360-370

On the Use of Semantic Annotations for Supporting Provenance in Grids.

Liming Chen, Zhuoan Jiao, Simon J. Cox

 371-380

Grid and Cluster Computing: Models, Middleware and Architectures

Topic 6: Grid and Cluster Computing: Models, Middleware and Architectures.

Domenico Laforenza, Alexander Reinefeld, Dieter Kranzlmüller, Luc Moreau

 381

Supporting Efficient Execution of MPI Applications Across Multiple Sites.

Enol Fernández, Elisa Heymann, Miquel A. Senar

 383-392

Private Virtual Cluster: Infrastructure and Protocol for Instant Grids.

Ala Rezmerita, Tangui Morlier, Vincent Néri, Franck Cappello

 393-404

Reducing Communication Overhead and Page Faults in SDSM Platforms.

Artemis A. Christopoulou, Eleftherios D. Polychronopoulos

 405-414

Flexible I/O Support for Reconfigurable Grid Environments.

Marc-André Hermanns, Rudolf Berrendorf, Marcel Birkner, Jan Seidel

 415-424

Storage Exchange: A Global Trading Platform for Storage Services.

Martin Placek, Rajkumar Buyya

 425-436

Vigne: Towards a Self-healing Grid Operating System.

Louis Rilling

 437-447

Problems for Resource Brokering in Large and Dynamic Grid Environments.

Catalin Dumitrescu

 448-458

Parallel Computer Architecture and Instruction Level Parallelism

Topic 7: Parallel Computer Architecture and Instruction Level Parallelism.

Eduard Ayguadé, Wolfgang Karl, Koen De Bosschere, Jean-Francois Collard

 459

Optimal Integrated VLIW Code Generation with Integer Linear Programming.

Andrzej Bednarski, Christoph W. Kessler

 461-472

Speeding-Up Synchronizations in DSM Multiprocessors.

Agustín De Dios Hernández, Benjamín Sahelices Fernández, Pablo Ibáñez, Víctor Viñals, José M. Llabería

 473-484

Design and Effectiveness of Small-Sized Decoupled Dispatch Queues.

Won Woo Ro, Jean-Luc Gaudiot

 485-494

Sim-async: An Architectural Simulator for Asynchronous Processor Modeling Using Distribution Functions.

José Manuel Colmenar, Oscar Garnica, Juan Lanchares, José Ignacio Hidalgo, Guadalupe Miñana, Sonia López

 495-505

A Hybrid Hardware/Software Generated Prefetching Thread Mechanism on Chip Multiprocessors.

Hou Rui, Longbing Zhang, Weiwu Hu

 506-516

Distributed Systems and Algorithms

Topic 8: Distributed Systems and Algorithms.

Andrzej Goscinski, Gudula Rünger, Edgar Gabriel, Christine Morin

 517

Distributed Approximation Allocation Resources Algorithm for Connecting Groups.

Fabien Baille, Lélia Blin, Christian Laforest

 519-529

Rollback-Recovery Protocol Guarantying MR Session Guarantee in Distributed Systems with Mobile Clients.

Jerzy Brzezinski, Anna Kobusinska, Michal Szychowiak

 530-538

A Practical Single-Register Wait-Free Mutual Exclusion Algorithm on Asynchronous Networks.

Hyungsoo Jung, Heon Young Yeom

 539-548

Optimal and Practical WAB-Based Consensus Algorithms.

Lásaro J. Camargos, Edmundo R. M. Madeira, Fernando Pedone

 549-558

Self-stabilizing Deadlock Detection Under the OR Requirement Model.

Christian F. Orellana, Cristian Ruz, Yadran Eterovic

 559-570

Incremental Distributed Garbage Collection Using Reverse Reference Tracking.

Michael Schöttner, Ralph Göckelmann, Stefan Frenz, Markus Fakler, Peter Schulthess

 571-581

Run-Time Switching Between Total Order Algorithms.

José Mocito, Luís Rodrigues

 582-591

On Greedy Graph Coloring in the Distributed Model.

Adrian Kosowski, Lukasz Kuszner

 592-601

Parallel Programming: Models, Methods and Languages

Topic 9: Parallel Programming: Models, Methods and Languages.

José C. Cunha, Sergei Gorlatch, Daniel J. Quinlan, Peter H. Welch

 603

Surrounding Theorem: Developing Parallel Programs for Matrix-Convolutions.

Kento Emoto, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi

 605-614

Dynamic Task Generation and Transformation Within a Nestable Workpool Skeleton.

Steffen Priebe

 615-624

Data Parallel Iterators for Hierarchical Grid and Tree Algorithms.

Gerhard W. Zumbusch

 625-634

Implementing Irregular Parallel Algorithms with OpenMP.

Michael Süß, Claudia Leopold

 635-644

Toward Enhancing OpenMP's Work-Sharing Directives.

Barbara M. Chapman, Lei Huang, Haoqiang Jin, Gabriele Jost, Bronis R. de Supinski

 645-654

Toward a Definition of and Linguistic Support for Partial Quiescence.

Billy Yan-Kit Man, Hiu Ning (Angela) Chan, Andrew J. Gallagher, Appu S. Goundan, Aaron W. Keen, Ronald A. Olsson

 655-665

Tying Memory Management to Parallel Programming Models.

Ioannis E. Venetis, Theodore S. Papatheodorou

 666-675

Parallel Numerical Algorithms

Topic 10: Parallel Numerical Algorithms.

Michel Cosnard, Hans-Joachim Bungartz, Efstratios Gallopoulos, Yousef Saad

 677-678

Parallel LOD Scheme for 3D Parabolic Problem with Nonlocal Boundary Condition.

Raimondas Ciegis

 679-688

Online Checkpointing for Parallel Adjoint Computation in PDEs: Application to Goal-Oriented Adaptivity and Flow Control.

Vincent Heuveline, Andrea Walther

 689-699

Parallel Fault Tolerant Algorithms for Parabolic Problems.

Hatem Ltaief, Marc Garbey, Edgar Gabriel

 700-709

Parallel Solution of Large-Scale and Sparse Generalized Algebraic Riccati Equations.

José M. Badía, Peter Benner, Rafael Mayo, Enrique S. Quintana-Ortí

 710-719

Applicability of Load Balancing Strategies to Data-Parallel Embedded Runge-Kutta Integrators.

Matthias Korch, Thomas Rauber

 720-729

A Software Framework for the Portable Parallelization of Particle-Mesh Simulations.

Ivo F. Sbalzarini, Jens H. Walther, B. Polasek, Philippe Chatelain, Michael Bergdorf, Simone Elke Hieber, Evangelos M. Kotsalis, Petros Koumoutsakos

 730-739

Parallelization of a Discrete Radiosity Method.

Rita Zrour, Pierre Y. Chatelier, Fabien Feschet, Rémy Malgouyres

 740-750

Parallelising Matrix Operations on Clusters for an Optimal Control-Based Quantum Compiler.

Tobias Gradl, A. Spörl, Thomas Huckle, Steffen J. Glaser, Thomas Schulte-Herbrüggen

 751-762

Distributed and High-Performance Multimedia

Topic 11: Distributed and High-Performance Multimedia.

Geoff Coulson, Harald Kosch, Odej Kao, Frank J. Seinstra

 763

Supporting Reconfigurable Parallel Multimedia Applications.

Maik Nijhuis, Herbert Bos, Henri E. Bal

 765-776

Providing VCR in a Distributed Client Collaborative Multicast Video Delivery Scheme.

Xiaoyuan Yang 0001, Porfidio Hernández, Fernando Cores, Ana Ripoll, Remo Suppi, Emilio Luque

 777-787

Linear Hashtable Motion Estimation Algorithm for Distributed Video Processing.

Yunsong Wu, Graham M. Megson

 788-797

Theory and Algorithms for Parallel Computation

Topic 12: Theory and Algorithms for Parallel Computation.

Danny Krizanc, Michael Kaufmann, Pierre Fraigniaud, Christos D. Zaroliagis

 799

A Hierarchical CLH Queue Lock.

Victor Luchangco, Daniel Nussbaum, Nir Shavit

 801-810

Competitive Freshness Algorithms for Wait-Free Data Objects.

Peter Damaschke, Phuong Hoai Ha, Philippas Tsigas

 811-820

A Parallel Algorithm for the Two-Dimensional Cutting Stock Problem.

Luis García, Coromoto León, Gara Miranda, Casiano Rodríguez

 821-830

A BSP/CGM Algorithm for Finding All Maximal Contiguous Subsequences of a Sequence of Numbers.

Carlos E. R. Alves, Edson Norberto Cáceres, Siang Wun Song

 831-840

On-Line Adaptive Parallel Prefix Computation.

Jean-Louis Roch, Daouda Traoré, Julien Bernard

 841-850

Routing and Communication in Interconnection Networks

Topic 13: Routing and Communication in Interconnection Networks.

José A. Gregorio, Bettina Schnor, Angelos Bilas, Olav Lysne

 851

A Model for the Development of AS Fabric Management Protocols.

Antonio Robles-Gómez, Eva M. García, Aurelio Bermúdez, Rafael Casado, Francisco J. Quiles

 853-863

On the Influence of the Selection Function on the Performance of Fat-Trees.

Francisco Gilabert Villamón, María Engracia Gómez, Pedro López, José Duato

 864-873

Scalable Ethernet Clos-Switches.

Norbert Eicker, Thomas Lippert

 874-883

Towards a Cost-Effective Interconnection Network Architecture with QoS and Congestion Management Support.

Alejandro Martínez, Pedro Javier García, Francisco José Alfaro, José L. Sánchez, Jose Flich, Francisco J. Quiles, José Duato

 884-895

Mobile and Ubiquitous Computing

Topic 14: Mobile and Ubiquitous Computing.

Alois Ferscha, Alexander Schill, GianLuigi Ferrari, Valérie Issarny

 897

Multi-rated Packet Transmission Scheme for IEEE 802.11 WLAN Networks.

Namgi Kim

 899-908

Comparison of Different Methods for Next Location Prediction.

Jan Petzold, Faruk Bagci, Wolfgang Trumler, Theo Ungerer

 909-918

SEER: Scalable Energy Efficient Relay Schemes in MANETs.

Lin-Fei Sung, Cheng-Lin Wu, Yi-Kai Chiang, Shyh-In Hwang

 919-930

Multicost Routing over an Infinite Time Horizon in Energy and Capacity Constrained Wireless Ad-Hoc Networks.

Christos A. Papageorgiou, Panagiotis C. Kokkinos, Emmanouel A. Varvarigos

 931-940

An Adaptive Self-organization Protocol for Wireless Sensor Networks.

Kil-Woong Jang, Byung-Soon Kim

 941-950

COPRA - A Communication Processing Architecture for Wireless Sensor Networks.

Reinhardt Karnapke, Jörg Nolte

 951-960

DAEDALUS - A Peer-to-Peer Shared Memory System for Ubiquitous Computing.

Peter Ibach, Vladimir Stantchev 0001, Christian Keller

 961-970

Context Awareness: An Experiment with Hoarding.

João Garcia, Luís Veiga, Paulo Ferreira

 971-980

A Client-Server Approach to Enhance Interactive Virtual Environments on Mobile Devices over Wireless Ad Hoc Networks.

Azzedine Boukerche, Richard Werner Nelem Pazzi, Tingxue Huang

 981-991

Peer-to-Peer and Web Computing

Topic 15: Peer-to-Peer and Web Computing.

Henrique João L. Domingos, Anne-Marie Kermarrec, Pascal Felber, Márk Jelasity

 993

Top k RDF Query Evaluation in Structured P2P Networks.

Dominic Battré, Felix Heine, Odej Kao

 995-1004

Roogle: Supporting Efficient High-Dimensional Range Queries in P2P Systems.

Di Wu, Ye Tian, Kam-Wing Ng

 1005-1014

Creating and Maintaining Replicas in Unstructured Peer-to-Peer Systems.

Elias Leontiadis, Vassilios V. Dimakopoulos, Evaggelia Pitoura

 1015-1025

DOH: A Content Delivery Peer-to-Peer Network.

Jimmy Jernberg, Vladimir Vlassov, Ali Ghodsi, Seif Haridi

 1026-1039

Applications of High-Performance and Grid Computing

Topic 16: Applications of High-Performance and Grid Computing.

Simon J. Cox, Thomas Lippert, Giovanni Erbacci, Denis Trystram

 1041

Task Pool Teams Implementation of the Master Equation Approach for Random Sierpinski Carpets.

Karl-Heinz Hoffmann, Michael Hofmann, Gudula Rünger, Steffen Seeger

 1043-1052

A Preliminary Out-of-Core Extension of a Parallel Multifrontal Solver.

Emmanuel Agullo, Abdou Guermouche, Jean-Yves L'Excellent

 1053-1063

A Parallel Adaptive Cartesian PDE Solver Using Space-Filling Curves.

Hans-Joachim Bungartz, Miriam Mehl, Tobias Weinzierl

 1064-1074

Load Balanced Parallel Simulated Annealing on a Cluster of SMP Nodes.

Agnieszka Debudaj-Grabysz, Rolf Rabenseifner

 1075-1084

A Grid Computing Based Virtual Laboratory for Environmental Simulations.

I. Ascione, Giulio Giunta, P. Mariani, Raffaele Montella, Angelo Riccio

 1085-1094

Exploiting Throughput for Pipeline Execution in Streaming Image Processing Applications.

Fernando Guirado, Ana Ripoll, Concepció Roig, Aura Hernandez, Emilio Luque

 1095-1105

dCache, Storage System for the Future.

Patrick Fuhrmann, Volker Gülzow

 1106-1113

Computing the Diameter of 17-Pancake Graph Using a PC Cluster.

Shogo Asai, Yuusuke Kounoike, Yuji Shinano, Keiichi Kaneko

 1114-1124

High-Performance Bioinformatics

Topic 17: High-Performance Bioinformatics.

Craig A. Stewart, Michael Schroeder, Concettina Guerra, Akihiko Konagaya

 1125-1126

Multidimensional Dynamic Programming for Homology Search on Distributed Systems.

Shingo Masuno, Tsutomu Maruyama, Yoshiki Yamaguchi, Akihiko Konagaya

 1127-1137

Load Balancing and Parallel Multiple Sequence Alignment with Tree Accumulation.

Guangming Tan, Liu Peng, Shengzhong Feng, Ninghui Sun

 1138-1147

ZIB Structure Prediction Pipeline: Composing a Complex Biological Workflow Through Web Services.

Patrick May, Hans-Christian Ehrlich, Thomas Steinke

 1148-1158

Evaluation of Parallel Paradigms on Anisotropic Nonlinear Diffusion.

Siham Tabik, Ester M. Garzón, Inmaculada García, José-Jesús Fernández

 1159-1168

Improving the Research Environment of High Performance Computing for Non-cluster Experts Based on Knoppix Instant Computing Technology.

Fumikazu Konishi, Manabu Ishii, Shingo Ohki, Yusuke Hamano, Shuichi Fukuda, Akihiko Konagaya

 1169-1178

Embedded Parallel Systems

Topic 18: Embedded Parallel Systems.

Jürgen Teich, Stefanos Kaxiras, Toomas P. Plaks, Krisztián Flautner

 1179

Efficient Realization of Data Dependencies in Algorithm Partitioning Under Resource Constraints.

Sebastian Siegel, Renate Merker

 1181-1191

FPGA Implementation of a Prototype Hierarchical Control Network for Large-Scale Signal Processing Applications.

Jérôme Lemaitre, Ed F. Deprettere

 1192-1203

An Embedded Systems Programming Environment for C.

Bernd Burgstaller, Bernhard Scholz, M. Anton Ertl

 1204-1216