Communication-aware processor allocation for supercomputers: Finding point sets of small average distance. (English) Zbl 1141.68017
Summary: We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops.
The associated clustering problem is as follows: Given \(n\) points in \(\mathfrak R^{d}\), find a size-\(k\) subset with minimum average pairwise \(L_{1}\) distance. We present a natural approximation algorithm and show that it is a \(\frac{7}{4}\)-approximation for two-dimensional grids; in \(d\) dimensions, the approximation guarantee is \(2-\frac{1}{2d}\), which is tight. We also give a polynomial-time approximation scheme for constant dimension \(d\), and we report on experimental results.
The associated clustering problem is as follows: Given \(n\) points in \(\mathfrak R^{d}\), find a size-\(k\) subset with minimum average pairwise \(L_{1}\) distance. We present a natural approximation algorithm and show that it is a \(\frac{7}{4}\)-approximation for two-dimensional grids; in \(d\) dimensions, the approximation guarantee is \(2-\frac{1}{2d}\), which is tight. We also give a polynomial-time approximation scheme for constant dimension \(d\), and we report on experimental results.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68W25 | Approximation algorithms |
Keywords:
Processor allocation; Supercomputers; Communication cost; Manhattan distance; Clustering; Approximation; Polynomial-time approximation schemeReferences:
| [1] | Ahmadinia, A., Bobda, C., Fekete, S.P., Teich, J., van der Veen, J.: Optimal free-space management and routing-conscious dynamic placement for reconfigurable computing. IEEE Trans. Comput. 56(5), 673–680 (2007) · doi:10.1109/TC.2007.1028 |
| [2] | Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum k-clustering in metric spaces. In: Proc. 33rd Symp. on Theory of Computation, pp. 11–20 (2001) · Zbl 1323.68565 |
| [3] | Baylor, S., Benveniste, C., Hsu, Y.: Performance evaluation of a massively parallel I/O subsystem. In: Jain, R., Werth, J., Browne, J. (eds.) Input/Output in Parallel and Distributed Computer Systems. The Kluwer International Series in Engineering and Computer Science, vol. 362, pp. 293–311. Kluwer Academic, Dordrecht (1996). Chapter 13 |
| [4] | Bender, C.M., Bender, M.A., Demaine, E., Fekete, S.: What is the optimal shape of a city?. J. Phys. A: Math. Gen. 37, 147–159 (2004) · Zbl 1046.90538 · doi:10.1088/0305-4470/37/1/010 |
| [5] | Bhattacharya, S., Tsai, W.-T.: Lookahead processor allocation in mesh-connected massively parallel computers. In: Proc. 8th International Parallel Processing Symposium, pp. 868–875 (1994) |
| [6] | Brightwell, R., Fisk, L.A., Greenberg, D.S., Hudson, T., Levenhagen, M., Maccabe, A.B., Riesen, R.: Massively parallel computing using commodity components. Parallel Comput. 26(2–3), 243–266 (2000) · Zbl 0939.68525 · doi:10.1016/S0167-8191(99)00104-0 |
| [7] | Chang, C., Mohapatra, P.: Improving performance of mesh connected multicomputers by reducing fragmentation. J. Parallel Distrib. Comput. 52(1), 40–68 (1998) · Zbl 0910.68018 · doi:10.1006/jpdc.1998.1459 |
| [8] | Chuang, P.-J., Tzeng, N.-F.: An efficient submesh allocation strategy for mesh computer systems. In: Proc. Int. Conf. Dist. Comp. Systems, pp. 256–263 (1991) |
| [9] | Feitelson, D.: The parallel workloads archive. http://www.cs.huji.ac.il/labs/parallel/workload/index.html |
| [10] | Fekete, S.P., Meijer, H.: Maximum dispersion and geometric maximum weight cliques. Algorithmica 38, 501–511 (2004) · Zbl 1095.68082 · doi:10.1007/s00453-003-1074-x |
| [11] | Guttmann-Beck, N., Hassin, R.: Approximation algorithms for minimum sum p-clustering. Discret. Appl. Math. 89, 125–142 (1998). http://www.math.tau.ac.il/ hassin/cluster.ps.gz · Zbl 0921.68044 · doi:10.1016/S0166-218X(98)00100-0 |
| [12] | Indyk, P.: A sublinear time approximation scheme for clustering in metric spaces. In: Proc. 40th Ann. IEEE Symp. Found. Comp. Sci. (FOCS), pp. 154–159 (1999). http://www.math.tau.ac.il/\(\sim\)hassin/cluster.ps.gz |
| [13] | Karp, R.M., McKellar, A.C., Wong, C.K.: Near-optimal solutions to a 2-dimensional placement problem. SIAM J. Comput. 4, 271–286 (1975) · Zbl 0355.68044 · doi:10.1137/0204023 |
| [14] | Krueger, P., Lai, T.-H., Dixit-Radiya, V.: Job scheduling is more important than processor allocation for hypercube computers. IEEE Trans. Parallel Distrib. Syst. 5(5), 488–497 (1994) · doi:10.1109/71.282559 |
| [15] | Krumke, S., Marathe, M., Noltemeier, H., Radhakrishnan, V., Ravi, S., Rosenkrantz, D.: Compact location problems. Theor. Comput. Sci. 181, 379–404 (1997) · Zbl 0902.90114 · doi:10.1016/S0304-3975(96)00304-0 |
| [16] | Leung, V., Arkin, E., Bender, M., Bunde, D., Johnston, J., Lal, A., Mitchell, J., Phillips, C., Seiden, S.: Processor allocation on Cplant: achieving general processor locality using one-dimensional allocation strategies. In: Proc. 4th IEEE International Conference on Cluster Computing, pp. 296–304 (2002) |
| [17] | Leung, V., Phillips, C., Bender, M., Bunde, D.: Algorithmic support for commodity-based parallel computing systems. Technical Report SAND2003-3702, Sandia National Laboratories (2003) |
| [18] | Li, K., Cheng, K.-H.: A two-dimensional buddy system for dynamic resource allocation in a partitionable mesh connected system. J. Parallel Distrib. Comput. 12, 79–83 (1991) · doi:10.1016/0743-7315(91)90032-5 |
| [19] | Lo, V., Windisch, K., Liu, W., Nitzberg, B.: Non-contiguous processor allocation algorithms for mesh-connected multicomputers. IEEE Trans. Parallel Distrib. Comput. 8(7) (1997) |
| [20] | Mache, J., Lo, V.: Dispersal metrics for non-contiguous processor allocation. Technical Report CIS-TR-96-13, University of Oregon (1996) |
| [21] | Mache, J., Lo, V.: The effects of dispersal on message-passing contention in processor allocation strategies. In: Proc. Third Joint Conf. on Information Sciences. Sessions on Parallel and Distributed Processing, vol. 3, pp. 223–226 (1997) |
| [22] | Mache, J., Lo, V., Windisch, K.: Minimizing message-passing contention in fragmentation-free processor allocation. In: Proc. 10th Intern. Conf. Parallel and Distributed Computing Systems, pp. 120–124 (1997) |
| [23] | Moore, S., Ni, L.: The effects of network contention on processor allocation strategies. In: Proc. 10th Int. Par. Proc. Symp., pp. 268–274 (1996) |
| [24] | Sahni, S., Gonzalez, T.: p-complete approximation problems. J. ACM 23(3), 555–565 (1976) · Zbl 0348.90152 · doi:10.1145/321958.321975 |
| [25] | Sandia National Laboratories: The Computational Plant Project. http://www.cs.sandia.gov/cplant |
| [26] | Subramani, V., Kettimuthu, R., Srinivasan, S., Johnson, J., Sadayappan, P.: Selective buddy allocation for scheduling parallel jobs on clusters. In: Proc. 4th IEEE International Conference on Cluster Computing (2002) · Zbl 1032.68545 |
| [27] | University of Oregon Resource Allocation Group: Procsimity. http://www.cs.uoregon.edu/research/DistributedComputing/ProcSimity.html |
| [28] | Weisser, D., Nystrom, N., Vizino, C., Brown, S.T., Urbanic, J.: Optimizing job placement on the Cray XT3. In: CUG 2006 Proceedings (2006) |
| [29] | Windisch, K., Miller, J., Lo, V.: Procsimity: an experimental tool for processor allocation and scheduling in highly parallel systems. In: Proc. Fifth Symp. on the Frontiers of Massively Parallel Computation, pp. 414–421 (1995). ftp://ftp.cs.uoregon.edu/pub/lo/procsimity.ps.gz |
| [30] | Zhu, Y.: Efficient processor allocation strategies for mesh-connected parallel computers. J. Parallel Distrib. Comput. 16, 328–337 (1992) · Zbl 0786.68016 · doi:10.1016/0743-7315(92)90016-G |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
