We illustrate the potential of techniques and results from the theory of network emulations to enhance the performance of a parallel architecture. The vehicle for this demonstration is a suite of algorithms that endow an N-processor bit-serial processor array A with a "meta-instruction" GAUGE k, which (logically) reconfigures A into an N/k-processor virtual machine B/sub k/ that has: 1) a datapath and memory bus whose emulated width is k bits, as opposed to A's 1-bit width and 2) an instruction set that operates on k-bit words, in contrast to A's instruction set, which operates on 1-bit words. In order to stress the strength of the approach, we show (via pseudocode) how our emulation techniques can be implemented efficiently even if A operates in strict SIMD mode, with only single-bit masking capabilities and with no indexed memory accesses. We describe at an algorithmic level how to implement our technique-including datapath conversion ("corner-turning") and the creation of the word-parallel instruction sets-on arrays of any regular network topology. We instantiate our technique in detail for arrays based on topologies with quite disparate characteristics: the hypercube, the de Bruijn network, and a genre of mesh with reconfigurable buses. Importantly, the emulations that underlie our technique do not alter the native machine's instruction set, hence allowing an invariant programming model across gauges.

Have1 and Liebl [1973], and Leighton 119841.' The networks of interest are defined in section 1.3.' For any graph 53, we denote by (%I the number of nodes in %.

Algorithms for embedding de Bruijn and shuffle-exchange graphs in books of five pages, with cumulative pagewidth $( 5/3 )2^n - ( 2/3 ) - ( 8/3 ) ( n\bmod 2 )$ and $( 5/6 )2^n + ( 2/3 ) - ( 4/3 ) ( n\bmod 2 )$, respectively, are presented. These are the first nontrivial bounds on the pagenumber of de Bruijn and shuffle-exchange graphs.

Article Free Access Share on Embedding de Bruijn and shuffle-exchange graphs in five pages (preliminary version) Author: Bojana Obrenic Computer and Information Science, University of Massachusetts, Amherst, MA Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 137–146https://doi.org/10.1145/113379.113392Published:01 June 1991Publication History 3citation296DownloadsMetricsTotal Citations3Total Downloads296Last 12 Months7Last 6 weeks3 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 An approach to emulating separable graphs (preliminary version) Share on Author: Bojana Obrenic Computer and Information Science, University of Massachusetts, Amherst, MA Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 159–167https://doi.org/10.1145/113379.113394Online:01 June 1991Publication History 0citation146DownloadsMetricsTotal Citations0Total Downloads146Last 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