Sorting and routing on r-dimensional n*. . .*n grids of processors is studied. Deterministic algorithms are presented for h-h problems, h>or=1, where each processor initially and finally contains h elements. It is shown that the classical 1-1 sorting can be solved with (2r-1.5)n+o(n) transport steps, i.e. in about 2.5n steps for r=2. The general h-h sorting problem, h>or=4r-4 can be solved within a number of transport steps that asymptotically differs by a factor of at most 3 from the trivial bisection bound. Furthermore, the bisection bound is asymptotically tight for sequences of h permutation routing problems, h=4cr, c>or=1, and for so-called offline routing.>

Article Free Access Share on Balanced routing: towards the distance bound on grids Author: Manfred Kunde Institut f. Informatik, TU Munich, Arcisstr. 21, D-8000 Munich 2, Germany Institut f. Informatik, TU Munich, Arcisstr. 21, D-8000 Munich 2, GermanyView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 260–271https://doi.org/10.1145/113379.113403Published:01 June 1991Publication History 7citation229DownloadsMetricsTotal Citations7Total Downloads229Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Multi-packet-routing on mesh connected arrays Share on Authors: M. Kunde Institut für Informatik, TU München, Arcisstr. 21, D-8000 München 2 Institut für Informatik, TU München, Arcisstr. 21, D-8000 München 2View Profile , T. Tensi Institut für Informatik, TU München, Arcisstr. 21, D-8000 München 2 Institut für Informatik, TU München, Arcisstr. 21, D-8000 München 2View Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 336–343https://doi.org/10.1145/72935.72971Online:01 March 1989Publication History 14citation255DownloadsMetricsTotal Citations14Total Downloads255Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Unequal execution time task systems are nonpreemptively scheduled on $m \geqq 2$ identical processors without additional resource constraints. Worst-case bounds for the ratio of the length of an LP-schedule (longest path) and an optimal schedule are given for two classes of dependency structures—chains and trees. Moreover, the asymptotic bounds, which are independent of the number of processors, are given for these classes and for anti-tree-systems.