×
Maggs, Bruce M.; Schwabe, Eric J.

Real-time emulations of bounded-degree networks. (English) Zbl 0925.68032

Inf. Process. Lett. 66, No. 5, 269-276 (1998).

Cited in 2 Documents

MSC:

68M10 Network design and communication in computer systems

Keywords:

bounded-degree processor networks; real-time and work-preserving emulations; interconnection networks
Cite Review PDF
Full Text: DOI

References:

[1] Achilles, A., Optimal emulation of meshes on meshes of trees, (Proc. EURO-PAR ’95 (1995)), 193-204
[2] Ajtai, M.; Komlós, J.; Szemerédi, E., Sorting in \(c log n\) parallel steps, Combinatorica, 3, 1-19 (1983) · Zbl 0523.68048
[3] Arora, S.; Leighton, F. T.; Maggs, B. M., On-line algorithms for path selection in a nonblocking network, SIAM J. Comput., 25, 3, 600-625 (1996) · Zbl 0852.68004
[4] Atallah, M. J., On multidimensional arrays of processors, IEEE Trans. Comput., 37, 10, 1306-1309 (1988) · Zbl 0658.68085
[5] Bassalygo, L. A.; Pinsker, M. S., Complexity of an optimum nonblocking switching network without reconnections, Probl. Inform. Transm., 9, 64-66 (1974) · Zbl 0327.94051
[6] Bay, P.; Bilardi, G., Deterministic on-line routing on area-universal networks, J. ACM, 42, 3, 614-640 (1995) · Zbl 0885.68029
[7] Bhatt, S. N.; Chung, F. R.K.; Hong, J.-W.; Leighton, F. T.; Obrenić, B.; Rosenberg, A. L.; Schwabe, E. J., Optimal emulations by butterfly-like networks, J. ACM, 43, 2, 293-330 (1996) · Zbl 0882.68006
[8] Bhatt, S. N.; Leighton, F. T., A framework for solving VLSI graph layout problems, J. Comput. Syst. Sci., 28, 2, 300-343 (1984) · Zbl 0543.68052
[9] Cole, R. J.; Maggs, B. M.; Sitaraman, R. K., Reconfiguring arrays with faults, Part I: Worst-case faults, SIAM J. Comput., 26, 6 (1997), to appear. · Zbl 0885.68011
[10] Feldmann, R.; Unger, W., The cube-connected cycles network is a subgraph of the butterfly network, Parallel Process. Lett., 2, 1, 13-19 (1992)
[11] Fellows, M. R., Encoding graphs in graphs, (Ph.D. Thesis (1985), Department of Computer Science, University of California: Department of Computer Science, University of California San Diego, CA)
[12] Greenberg, R. I.; Leiserson, C. E., Randomized routing on fattrees, (Micali, S., Randomness and Computation. Randomness and Computation, Advances in Computing Research, Vol. 5 (1989), JAI Press: JAI Press Greenwich, CT), 345-374
[13] Koch, R. R.; Leighton, F. T.; Maggs, B. M.; Rao, S. B.; Rosenberg, A. L.; Schwabe, E. J., Work-preserving emulations of fixed-connection networks, J. ACM, 44, 1, 104-147 (1997) · Zbl 0883.68011
[14] Kruskal, C. P.; Rappoport, K. J., Bandwidth-based lower bounds on slowdown for efficient emulations of fixed-connection networks, (Proc. 6th Ann. ACM Symposium on Parallel Algorithms and Architectures (1994)), 132-139
[15] Leighton, F. T., Complexity Issues in VLSI (1983), MIT Press: MIT Press Cambridge, MA
[16] Leighton, F. T., Tight bounds on the complexity of parallel sorting, IEEE Trans. Comput., C-34, 4, 344-354 (1985) · Zbl 0556.68024
[17] Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays • Trees • Hypercubes (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA · Zbl 0743.68007
[18] Leighton, F. T.; Maggs, B. M., Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks, IEEE Trans. Comput., 41, 5, 578-587 (1992)
[19] Leighton, F. T.; Maggs, B. M.; Ranade, A. G.; Rao, S. B., Randomized routing and sorting on fixed-connection networks, J. Algorithms, 17, 1, 157-205 (1994) · Zbl 0808.68048
[20] Leiserson, C. E., Fat-trees: Universal networks for hardware-efficient supercomputing, IEEE Trans. Comput., C-34, 10, 892-901 (1985)
[21] Maggs, B. M.; Vöcking, B., Improved routing and sorting on multibutterflies, (Proc. 29th Annual ACM Symposium on Theory of Computing (1997)), 517-530 · Zbl 0963.68005
[22] der Heide, F. Meyer auf, Efficiency of universal parallel computers, Acta Informatica, 19, 269-296 (1983) · Zbl 0489.68017
[23] der Heide, F. Meyer auf, Efficient simulations among several models of parallel computers, SIAM J. Comput., 15, 1, 106-119 (1986) · Zbl 0545.68043
[24] der Heide, F. Meyer auf; Wanka, R., Time-optimal simulations of networks by universal parallel computers, (Proc. 6th Symposium on Theoretical Aspects of Computer Science. Proc. 6th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci., Vol. 349 (1989), Springer: Springer Heidelberg), 120-131 · Zbl 1492.68032
[25] Paterson, M. S., Improved sorting networks with \(O( log N)\) depth, Algorithmica, 5, 75-92 (1990) · Zbl 0689.68066
[26] Preparata, F. P.; Vuillemin, J. E., The cube-connected cycles: A versatile network for parallel computation, Comm. ACM, 24, 5, 300-309 (1981)
[27] Rappoport, K. J., On the slowdown of efficient simulations of multibutterflies, (Proc. 8th Annual ACM Symposium on Parallel Algorithms and Architectures (1996)), 176-182
[28] Schwabe, E. J., Embedding meshes of trees into deBruijn graphs, Inform. Process. Lett., 43, 5, 237-240 (1992) · Zbl 0764.68131
[29] Schwabe, E. J., Constant-slowdown simulations of normal hypercube algorithms on the butterfly network, Inform. Process. Lett., 45, 2, 295-301 (1993) · Zbl 0771.68058
[30] Sekanina, M., On an ordering of the set of vertices of a connected graph, Publ. Fac. Sci. Univ. Brno, 412, 137-142 (1960) · Zbl 0118.18903
[31] Stone, H., Parallel processing with the perfect shuffle, IEEE Trans. Comput., C-20, 2, 153-161 (1971) · Zbl 0214.42703
[32] Upfal, E., An \(O( log N)\) deterministic packet routing scheme, J. ACM, 39, 1, 55-70 (1992) · Zbl 0799.68105
[33] Zhang, L., Emulations and embeddings of meshes of trees and hypercubes of cliques, (Ph.D. Thesis (1995), University of Waterloo: University of Waterloo Waterloo, Ontarioerloo)
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.