@inproceedings{83be5aad682b46708341279833979b8f,
title = "Shorter queues for permutation routing on meshes",
abstract = "New deterministic algorithms for routing permutations on an n ×n MIMD mesh are presented. They are very efficient in terms of the size of auxiliary memory at each processor, measured as the maximum number of packets that need to be queued. One algorithm runs in the optimal time 2·n-2 with a maximum queue length of 33. Another runs in the near-optimal time 2·n + O(1) with a maximum queue length of only 12. The attained queue sizes are less than half of the previously best queue bounds. The improvements in the queue sizes are due to a new general routing scheme, a better scattering algorithm, and a new technique called spreading.",
author = "Sibeyn, {Jop F.} and Chlebus, {Bogdan S.} and Michael Kaufmann",
year = "1994",
doi = "10.1007/3-540-58338-6_106",
language = "English (US)",
isbn = "9783540583387",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "597--607",
editor = "Igor Privara and Branislav Rovan and Peter Ruzicka",
booktitle = "Mathematical Foundations of Computer Science 1994 - 19th International Symposium, MFCS 1994, Proceedings",
note = "19th International Symposium on Mathematical Foundations of Computer Science, MFCS 1994 ; Conference date: 22-08-1994 Through 26-08-1994",
}