Parallel Computing (TOPC)


Search Issue
enter search term and/or author name


ACM Transactions on Parallel Computing - Special Issue on SPAA 2012, Volume 2 Issue 1, May 2015

Guest Editor Introduction
Maurice Herlihy
Article No.: 1
DOI: 10.1145/2716306

Linear and Competitive Strategies for Continuous Robot Formation Problems
Bastian Degener, Barbara Kempkes, Peter Kling, Friedhelm Meyer Auf Der Heide
Article No.: 2
DOI: 10.1145/2742341

We study a scenario in which n mobile robots with a limited viewing range are distributed in the Euclidean plane and have to solve a formation problem. The formation problems we consider are the Gathering problem and the...

Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing Clusters
Navendu Jain, Ishai Menache, Joseph (Seffi) Naor, Jonathan Yaniv
Article No.: 3
DOI: 10.1145/2742343

We consider a market-based resource allocation model for batch jobs in cloud computing clusters. In our model, we incorporate the importance of the due date of a job rather than the number of servers allocated to it at any given time. Each batch...

Hedonic Clustering Games
Moran Feldman, Liane Lewin-Eytan, Joseph (Seffi) Naor
Article No.: 4
DOI: 10.1145/2742345

Clustering, the partitioning of objects with respect to a similarity measure, has been extensively studied as a global optimization problem. We investigate clustering from a game-theoretic approach, and consider the class of hedonic clustering...

Runtime Resource Allocation for Software Pipelines
Janmartin Jahn, Santiago Pagani, Sebastian Kobbe, Jian-Jia Chen, Jörg Henkel
Article No.: 5
DOI: 10.1145/2742347

Efficiently allocating the computational resources of many-core systems is one of the most prominent challenges, especially when resource requirements may vary unpredictably at runtime. This is even more challenging when facing unreliable...

Simple Virtual Channel Allocation for High-Throughput and High-Frequency On-Chip Routers
Yi Xu, Bo Zhao, Youtao Zhang, Jun Yang
Article No.: 6
DOI: 10.1145/2742349

Packet-switched network-on-chip (NoC) has provided a scalable solution to the communications for tiled multicore processors. However, the virtual channel (VC) buffers in the NoC consume significant dynamic and leakage power. To improve the energy...

Noise-Tolerant Explicit Stencil Computations for Nonuniform Process Execution Rates
Adam Hammouda, Andrew R. Siegel, Stephen F. Siegel
Article No.: 7
DOI: 10.1145/2742351

Next-generation HPC computing platforms are likely to be characterized by significant, unpredictable nonuniformities in execution time among compute nodes and cores. The resulting load imbalances from this nonuniformity are expected to arise from...

The Shape of the Search Tree for the Maximum Clique Problem and the Implications for Parallel Branch and Bound
Ciaran McCreesh, Patrick Prosser
Article No.: 8
DOI: 10.1145/2742359

Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multicore thread-parallel adaptations of a state-of-the-art branch-and-bound algorithm for the maximum clique problem and provide a novel...