×

Models and resource metrics for parallel simulated annealing for the graph-partitioning problem. (English) Zbl 1049.68943

MSC:

68W15 Distributed algorithms
68W10 Parallel algorithms in computer science
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Aggarwal , B. Alpern , A. Chandra and M. Snir , A model for hierarchical memory . InProc. 19th ACM Symp. on Theory of Computing, May 1987 , 305 – 314 .
[2] Alpern B., Portability and Performance for Parallel Processing pp 21– (1994)
[3] DOI: 10.1007/BF01185206 · Zbl 0938.68638 · doi:10.1007/BF01185206
[4] A. Aggarwal,A. ChandraandM. Snir,Hierarchical memory with block transfer. InProc. 28th Symp. on Foundations of Computer Science,Oct.1987,204–216.
[5] Aggarwal A., J. Theoretical Computer Science (1990)
[6] A. Aggarwal , A. Chandra and M. Snir , On communication latency in PRAM computation . InProc. 1st ACM Symp. on Parallel Algorithms and Architectures, 1989 , 11 – 21 .
[7] DOI: 10.1145/48529.48535 · doi:10.1145/48529.48535
[8] DOI: 10.1145/135226.135227 · doi:10.1145/135226.135227
[9] Blelloch G. E., Vector Models for Data-Parallel Computing (1990)
[10] A. Bar-Noy and S. Kipnis , Designing broadcasting algorithms in the Postal model for message-passing systems . InProc. 4th ACM Symp. on Parallel Algorithms and Architectures, ACM , June 1992 , 11 – 22 . · Zbl 0812.68079
[11] J. Celuch , The 9076 SP1 high-performance communication network, Technical Report, KGNVMC , Kingston , 1994 .
[12] D. Culler , R. Karp , D. Patterson , A. Sahay , K. E. Schauser , E. Santos , R. Subramonian and T. von Eicken , LogP Towards a realistic model of parallel computation . InProc. 4th ACM Symp. on Principles and Practice of Parallel Programming, ACM , 1993 , 1 – 12 .
[13] R. Cole and O. Zajicek , The APRAM Incorporating asynchrony into the PRAM model . InProc. 1st ACM Symp. on Parallel Algorithms and Architectures, ACM , 1989 , 169 – 178 .
[14] R. Cole and O. Zajicek , The expected advantage of asynchrony . InProc. 2nd ACM Symp. on Parallel Algorithms and Architectures, ACM , 1990 , 85 – 94 . · Zbl 0831.68047
[15] S. Fortune and J. Wyllie , Parallelism in random access machines . InProc. 10th ACM Symp. on Theory of Computing, 1978 , 114 – 118 . · Zbl 1282.68104
[16] P. B. Gibbons , A more practical PRAM model . InProc. 1st ACM Symp. on Parallel Algorithms and Architectures, ACM , 1989 , 158 – 168 .
[17] P. B. Gibbons , Y. Matias and V. Ramachandran , The QRQW PRAM Accounting for contention in parallel algorithms . InProc. 5th ACM-SIAM Symp. on Discrete Algorithms, 1994 , 638 – 647 . · Zbl 0871.68094
[18] DOI: 10.1145/164996.165002 · doi:10.1145/164996.165002
[19] JáJá J., An Introduction to Parallel Algorithms (1992) · Zbl 0781.68009
[20] R. Karp , A. Sahay , E. Santos and K. Schauser . Optimal broadcast and summation in the LogP model . InProc. 5th ACM Symp. on Parallel Algorithms and Architectures, 1993 , 142 – 153 .
[21] DOI: 10.1109/TC.1985.5009385 · Zbl 0556.68024 · doi:10.1109/TC.1985.5009385
[22] Loan C. V., Computational Frameworks for the Fast Fourier Transform (1992) · Zbl 0757.65154 · doi:10.1137/1.9781611970999
[23] M. Nodine and J. Vitter , Large-scale sorting in parallel memories . InProc. 3rd ACM Symp. on Parallel Algorithms and Architectures, July 1991 , 29 – 39 .
[24] DOI: 10.1145/358645.358660 · doi:10.1145/358645.358660
[25] Reif J., Synthesis of Parallel Algorithms (1993)
[26] A. Sahay , Hiding communication costs in bandwidth-limited parallel FFT computation , Technical Report UCB/CSD 92/722 , UC Berkeley , 1992 .
[27] C. Stunkel , D. Dhea , D. Grice , P. Hochschild and M. Tsao , The SP1 high-performance switch . InProc. of the Scalable High Performance Computing Conference( Knoxville , TN ), May 1994 , 150 – 157 .
[28] DOI: 10.1007/BF01407840 · doi:10.1007/BF01407840
[29] DOI: 10.1146/annurev.cs.01.060186.001445 · doi:10.1146/annurev.cs.01.060186.001445
[30] Thinking Machine Corporation, DPEAC reference manual , 1992 .
[31] DOI: 10.1145/79173.79181 · doi:10.1145/79173.79181
[32] J. Vitter and E. Shriver , Optimal disk I/O with parallel block transfer . InProc. 22nd ACM Symp. on Theory of Computing, 1990 , 159 – 169 . · Zbl 0917.68086
[33] DOI: 10.1007/BF01185208 · Zbl 0917.68086 · doi:10.1007/BF01185208
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.