@article {17980,
	title = {A Low-Overhead Asynchronous Interconnection Network for GALS Chip Multiprocessors},
	journal = {Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on},
	volume = {30},
	year = {2011},
	month = {2011/04//},
	pages = {494 - 507},
	abstract = {A new asynchronous interconnection network is introduced for globally-asynchronous locally-synchronous (GALS) chip multiprocessors. The network eliminates the need for global clock distribution, and can interface multiple synchronous timing domains operating at unrelated clock rates. In particular, two new highly-concurrent asynchronous components are introduced which provide simple routing and arbitration/merge functions. Post-layout simulations in identical commercial 90 nm technology indicate that comparable recent synchronous router nodes have 5.6-10.7 more energy per packet and 2.8-6.4 greater area than the new asynchronous nodes. Under random traffic, the network provides significantly lower latency and identical throughput over the entire operating range of the 800 MHz network and through mid-range traffic rates for the 1.36 GHz network, but with degradation at higher traffic rates. Preliminary evaluations are also presented for a mixed-timing (GALS) network in a shared-memory parallel architecture, running both random traffic and parallel benchmark kernels, as well as directions for further improvement.},
	keywords = {1.36, 800, 90, architecture;size, architectures;shared, asynchronous, benchmark, chip, chips;multiprocessor, distribution, distribution;frequency, GALS, GHz;frequency, interconnection, kernel;post-layout, layout;clock, locally-synchronous, memory, MHz;globally-asynchronous, multiple, multiprocessor;clock, multiprocessor;interface, network;mixed-timing, network;network, networks;microprocessor, networks;network, nm;circuit, Parallel, routing;network-on-chip;parallel, routing;parallel, simulation;random, synchronous, systems;, timing;low-overhead, traffic;shared-memory},
	isbn = {0278-0070},
	doi = {10.1109/TCAD.2011.2114970},
	author = {Horak,M.N. and Nowick,S.M. and Carlberg,M. and Vishkin, Uzi}
}
@conference {15005,
	title = {Optimization of linked list prefix computations on multithreaded GPUs using CUDA},
	booktitle = {Parallel Distributed Processing (IPDPS), 2010 IEEE International Symposium on},
	year = {2010},
	month = {2010/04//},
	pages = {1 - 8},
	abstract = {We present a number of optimization techniques to compute prefix sums on linked lists and implement them on multithreaded GPUs using CUDA. Prefix computations on linked structures involve in general highly irregular fine grain memory accesses that are typical of many computations on linked lists, trees, and graphs. While the current generation of GPUs provides substantial computational power and extremely high bandwidth memory accesses, they may appear at first to be primarily geared toward streamed, highly data parallel computations. In this paper, we introduce an optimized multithreaded GPU algorithm for prefix computations through a randomization process that reduces the problem to a large number of fine-grain computations. We map these fine-grain computations onto multithreaded GPUs in such a way that the processing cost per element is shown to be close to the best possible. Our experimental results show scalability for list sizes ranging from 1M nodes to 256M nodes, and significantly improve on the recently published parallel implementations of list ranking, including implementations on the Cell Processor, the MTA-8, and the NVIDIA GeForce 200 series. They also compare favorably to the performance of the best known CUDA algorithm for the scan operation on the Tesla C1060.},
	keywords = {200, accesses;fine, accesses;linked, Bandwidth, C1060;cell, computations;extremely, computations;multithreaded, CUDA;MTA;NVIDIA, GeForce, GPUs;optimization;prefix, grain, high, list, memory, Parallel, prefix, process;coprocessors;multi-threading;, processor;data, series;Tesla, sums;randomization},
	doi = {10.1109/IPDPS.2010.5470455},
	author = {Wei, Zheng and JaJa, Joseph F.}
}
@conference {17984,
	title = {Resource-Aware Compiler Prefetching for Many-Cores},
	booktitle = {Parallel and Distributed Computing (ISPDC), 2010 Ninth International Symposium on},
	year = {2010},
	month = {2010/07//},
	pages = {133 - 140},
	abstract = {Super-scalar, out-of-order processors that can have tens of read and write requests in the execution window place significant demands on Memory Level Parallelism (MLP). Multi-and many-cores with shared parallel caches further increase MLP demand. Current cache hierarchies however have been unable to keep up with this trend, with modern designs allowing only 4-16 concurrent cache misses. This disconnect is exacerbated by recent highly parallel architectures (e.g. GPUs) where power and area per-core budget favor lighter cores with less resources. Support for hardware and software prefetch increase MLP pressure since these techniques overlap multiple memory requests with existing computation. In this paper, we propose and evaluate a novel Resource-Aware Prefetching (RAP) compiler algorithm that is aware of the number of simultaneous prefetches supported, and optimized for the same. We show that in situations where not enough resources are available to issue prefetch instructions for all references in a loop, it is more beneficial to decrease the prefetch distance and prefetch for as many references as possible, rather than use a fixed prefetched distance and skip prefetching for some references, as in current approaches. We implemented our algorithm in a GCC-derived compiler and evaluated its performance using an emerging fine-grained many-core architecture. Our results show that the RAP algorithm outperforms a well-known loop prefetching algorithm by up to 40.15\% and the state-of-the art GCC implementation by up to 34.79\%. Moreover, we compare the RAP algorithm with a simple hardware prefetching mechanism, and show improvements of up to 24.61\%.},
	keywords = {algorithm;memory, architecture;hardware-software, architectures;parallel, architectures;resource, aware, caches;super-scalar, compiler, compiler;Multicore, compilers;parallel, GCC-derived, level, management;, many-core, memories;storage, out-of-order, Parallel, parallelism;parallel, prefetch;loop, prefetching, prefetching;shared, processor;fine-grained, processors;multiprocessing, systems;optimising},
	doi = {10.1109/ISPDC.2010.16},
	author = {Caragea,G.C. and Tzannes,A. and Keceli,F. and Barua,R. and Vishkin, Uzi}
}
@article {17990,
	title = {Mesh-of-Trees and Alternative Interconnection Networks for Single-Chip Parallelism},
	journal = {Very Large Scale Integration (VLSI) Systems, IEEE Transactions on},
	volume = {17},
	year = {2009},
	month = {2009/10//},
	pages = {1419 - 1432},
	abstract = {In single-chip parallel processors, it is crucial to implement a high-throughput low-latency interconnection network to connect the on-chip components, especially the processing units and the memory units. In this paper, we propose a new mesh of trees (MoT) implementation of the interconnection network and evaluate it relative to metrics such as wire complexity, total register count, single switch delay, maximum throughput, tradeoffs between throughput and latency, and post-layout performance. We show that on-chip interconnection networks can provide higher bandwidth between processors and shared first-level cache than previously considered possible, facilitating greater scalability of memory architectures that require that. MoT is also compared, both analytically and experimentally, to some other traditional network topologies, such as hypercube, butterfly, fat trees and butterfly fat trees. When we evaluate a 64-terminal MoT network at 90-nm technology, concrete results show that MoT provides higher throughput and lower latency especially when the input traffic (or the on-chip parallelism) is high, at comparable area. A recurring problem in networking and communication is that of achieving good sustained throughput in contrast to just high theoretical peak performance that does not materialize for typical work loads. Our quantitative results demonstrate a clear advantage of the proposed MoT network in the context of single-chip parallel processing.},
	keywords = {90, cache;single, complexity;multiprocessor, delay;single-chip, first-level, high-throughput, interconnection, low-latency, network;memory, network;shared, networks;network-on-chip;parallel, nm;wire, Parallel, parallelism;size, processing;, processor;single-chip, switch, topologies;on-chip, units;mesh-of-trees;network},
	isbn = {1063-8210},
	doi = {10.1109/TVLSI.2008.2003999},
	author = {Balkan,A.O. and Gang Qu and Vishkin, Uzi}
}
@article {12158,
	title = {The ASC-Alliance Projects: A Case Study of Large-Scale Parallel Scientific Code Development},
	journal = {Computer},
	volume = {41},
	year = {2008},
	month = {2008/03//},
	pages = {50 - 58},
	abstract = {Computational scientists face many challenges when developing software that runs on large-scale parallel machines. However, software-engineering researchers haven{\textquoteright}t studied their software development processes in much detail. To better understand the nature of software development in this context, the authors examined five large-scale computational science software projects operated at the five ASC-Alliance centers.},
	keywords = {ASC-Alliance, code, development;large-scale, development;parallel, engineering;, machines;software, Parallel, projects;computational, scale, Science, scientific, scientists;large, software, systems;parallel},
	isbn = {0018-9162},
	doi = {10.1109/MC.2008.101},
	author = {Hochstein, L. and Basili, Victor R.}
}
@article {17930,
	title = {Parallel, stochastic measurement of molecular surface area},
	journal = {Journal of Molecular Graphics and Modelling},
	volume = {27},
	year = {2008},
	month = {2008/08//},
	pages = {82 - 87},
	abstract = {Biochemists often wish to compute surface areas of proteins. A variety of algorithms have been developed for this task, but they are designed for traditional single-processor architectures. The current trend in computer hardware is towards increasingly parallel architectures for which these algorithms are not well suited.We describe a parallel, stochastic algorithm for molecular surface area computation that maps well to the emerging multi-core architectures. Our algorithm is also progressive, providing a rough estimate of surface area immediately and refining this estimate as time goes on. Furthermore, the algorithm generates points on the molecular surface which can be used for point-based rendering.
We demonstrate a GPU implementation of our algorithm and show that it compares favorably with several existing molecular surface computation programs, giving fast estimates of the molecular surface area with good accuracy.
},
	keywords = {gpu, Molecular surface, Parallel, Progressive, Quasi-random, Stochastic},
	isbn = {1093-3263},
	doi = {10.1016/j.jmgm.2008.03.001},
	url = {http://www.sciencedirect.com/science/article/pii/S1093326308000387},
	author = {Juba,Derek and Varshney, Amitabh}
}
@conference {18000,
	title = {Layout-Accurate Design and Implementation of a High-Throughput Interconnection Network for Single-Chip Parallel Processing},
	booktitle = {High-Performance Interconnects, 2007. HOTI 2007. 15th Annual IEEE Symposium on},
	year = {2007},
	month = {2007/08//},
	pages = {21 - 28},
	abstract = {A mesh of trees (MoT) on-chip interconnection network has been proposed recently to provide high throughput between memory units and processors for single-chip parallel processing (Balkan et al., 2006). In this paper, we report our findings in bringing this concept to silicon. Specifically, we conduct cycle-accurate Verilog simulations to verify the analytical results claimed in (Balkan et al., 2006). We synthesize and obtain the layout of the MoT interconnection networks of various sizes. To further improve throughput, we investigate different arbitration primitives to handle load and store, the two most common memory operations. We also study the use of pipeline registers in large networks when there are long wires. Simulation based on full network layout demonstrates that significant throughput improvement can be achieved over the original proposed MoT interconnection network. The importance of this work lies in its validation of performance features of the MoT interconnection network, as they were previously shown to be competitive with traditional network solutions. The MoT network is currently used in an eXplicit multi-threading (XMT) on-chip parallel processor, which is engineered to support parallel programming. In that context, a 32-terminal MoT network could support up to 512 on-chip XMT processors. Our 8-terminal network that could serve 8 processor clusters (or 128 total processors), was also accepted recently for fabrication.},
	keywords = {description, design;mesh, interconnection, languages;multi-threading;multiprocessor, MoT, multi-threading;layout-accurate, network;on-chip, network;Verilog, networks;parallel, of, on-chip, Parallel, processing;, processing;hardware, processor;parallel, processors;on-chip, programming;pipeline, registers;single-chip, simulations;eXplicit, TREES, XMT},
	doi = {10.1109/HOTI.2007.11},
	author = {Balkan,A.O. and Horak,M.N. and Gang Qu and Vishkin, Uzi}
}
@conference {12648,
	title = {Algorithmic and architectural design methodology for particle filters in hardware},
	booktitle = {Computer Design: VLSI in Computers and Processors, 2005. ICCD 2005. Proceedings. 2005 IEEE International Conference on},
	year = {2005},
	month = {2005/10//},
	pages = {275 - 280},
	abstract = {In this paper, we present algorithmic and architectural methodology for building particle filters in hardware. Particle filtering is a new paradigm for filtering in presence of nonGaussian nonlinear state evolution and observation models. This technique has found wide-spread application in tracking, navigation, detection problems especially in a sensing environment. So far most particle filtering implementations are not lucrative for real time problems due to excessive computational complexity involved. In this paper, we re-derive the particle filtering theory to make it more amenable to simplified VLSI implementations. Furthermore, we present and analyze pipelined architectural methodology for designing these computational blocks. Finally, we present an application using the bearing only tracking problem and evaluate the proposed architecture and algorithmic methodology.},
	keywords = {(numerical, algorithmic, architectural, architectures;, bearing, complexity;, computational, design, digital, evolution;, Filtering, filtering;, filters;, implementation;, methodology;, methods);, nonGaussian, nonlinear, only, Parallel, particle, pipeline, pipelined, problem;, processing;, state, tracking, VLSI, VLSI;},
	doi = {10.1109/ICCD.2005.20},
	author = {Sankaranarayanan,A. C and Chellapa, Rama and Srivastava, A.}
}
@conference {15029,
	title = {Strategies for exploring large scale data},
	booktitle = {Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on},
	year = {2004},
	month = {2004/05//},
	pages = {2 - 2},
	abstract = {We consider the problem of querying large scale multidimensional time series data to discover events of interest, test and validate hypotheses, or to associate temporal patterns with specific events. This type of data currently dominates most other types of available data, and will very likely become even more prevalent in the future given the current trends in collecting time series of business, scientific, demographic, and simulation data. The ability to explore such collections interactively, even at a coarse level, will be critical in discovering the information and knowledge embedded in such collections. We develop indexing techniques and search algorithms to efficiently handle temporal range value querying of multidimensional time series data. Our indexing uses linear space data structures that enable the handling of queries in I/O time that is essentially the same as that of handling a single time slice, assuming the availability of a logarithmic number of processors as a function of the temporal window. A data structure with provably almost optimal asymptotic bounds is also presented for the case when the number of multidimensional objects is relatively small. These techniques improve significantly over standard techniques for either serial or parallel processing, and are evaluated by extensive experimental results that confirm their superior performance.},
	keywords = {algorithms;, association;, asymptotic, bounds;, business, data, data;, database, databases;, demographic, discovery;, Indexing, indexing;, information, knowledge, large, linear, mining;, multidimensional, objects;, optimal, Parallel, pattern, processing;, query, querying;, range, scale, scientific, search, serial, series, series;, simulation, space, structure;, structures;, techniques;, temporal, TIME, value, very, window;},
	doi = {10.1109/ISPAN.2004.1300447},
	author = {JaJa, Joseph F.}
}
@article {14935,
	title = {A perspective on Quicksort},
	journal = {Computing in Science Engineering},
	volume = {2},
	year = {2000},
	month = {2000/02//jan},
	pages = {43 - 49},
	abstract = {This article introduces the basic Quicksort algorithm and gives a flavor of the richness of its complexity analysis. The author also provides a glimpse of some of its generalizations to parallel algorithms and computational geometry},
	keywords = {algorithm;, algorithms;, analysis;, complexity, complexity;, computational, geometry;, Parallel, Quicksort, sorting;},
	isbn = {1521-9615},
	doi = {10.1109/5992.814657},
	author = {JaJa, Joseph F.}
}
@article {14988,
	title = {Models and high-performance algorithms for global BRDF retrieval},
	journal = {Computational Science Engineering, IEEE},
	volume = {5},
	year = {1998},
	month = {1998/12//oct},
	pages = {16 - 29},
	abstract = {The authors describe three models for retrieving information related to the scattering of light on the Earth{\textquoteright}s surface. Using these models, they{\textquoteright}ve developed algorithms for the IBM SP2 that efficiently retrieve this information},
	keywords = {algorithms;, BRDF, Earth, geomorphology;, geophysical, global, high-performance, IBM, information, light, machines;, models;, Parallel, processing;, reflectivity;, retrieval, retrieval;, scattering;, signal, SP2;, surface;},
	isbn = {1070-9924},
	doi = {10.1109/99.735892},
	author = {Zengyan Zhang and Kalluri, SNV and JaJa, Joseph F. and Liang,Shunlin and Townshend,J.R.G.}
}
@conference {14995,
	title = {On combining technology and theory in search of a parallel computation model},
	booktitle = {Parallel Processing, 1996. Proceedings of the 1996 ICPP Workshop on Challenges for},
	year = {1996},
	month = {1996/08//},
	pages = {115 - 123},
	abstract = {A fundamental problem in parallel computing is to design high-level, architecture independent, algorithms that execute efficiently on general purpose parallel machines. The aim is to be able to achieve portability and high performance simultaneously. A key to accomplishing this is the existence of a computation model that can bridge the gap between the high level programming models and the underlying hardware models. There are currently two factors that make this fundamental problem more tractable. The first is the emergence of a dominant parallel architecture consisting of a number of powerful microprocessors interconnected by either a proprietary interconnect, or a standard off-the-shelf interconnect (such as an ATM switch). The second factor is the emergence of standards, such as the message passing standard MPI, for which efficient implementations are either available or about to appear on most machines. Our recent work has exploited these two developments by developing a methodology based on (1) a simple computation model for the current MIMD platforms that incorporates communication cost into the complexity of the algorithms, and (2) a SPMD programming model that makes effective use of communication primitives. We describe our approach for validating the computation model based on extensive experimentation and the development of benchmarks, and discuss its extension to the emerging clusters of Symmetric Multiprocessors (SMPs) architecture},
	keywords = {algorithms;parallel, architectures;parallel, COMPUTATION, computing;portability;parallel, machines;, machines;high, MIMD, model;parallel, Multiprocessors;general, Parallel, performance;parallel, platforms;Symmetric, purpose},
	doi = {10.1109/ICPPW.1996.538597},
	author = {JaJa, Joseph F.}
}
@conference {18038,
	title = {Efficient approximate and dynamic matching of patterns using a labeling paradigm},
	booktitle = {Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on},
	year = {1996},
	month = {1996/10//},
	pages = {320 - 328},
	abstract = {A key approach in string processing algorithmics has been the labeling paradigm which is based on assigning labels to some of the substrings of a given string. If these labels are chosen consistently, they can enable fast comparisons of substrings. Until the first optimal parallel algorithm for suffix tree construction was given by the authors in 1994 the labeling paradigm was considered not to be competitive with other approaches. They show that this general method is also useful for several central problems in the area of string processing: approximate string matching, dynamic dictionary matching, and dynamic text indexing. The approximate string matching problem deals with finding all substrings of a text which match a pattern ldquo;approximately rdquo;, i.e., with at most m differences. The differences can be in the form of inserted, deleted, or replaced characters. The text indexing problem deals with finding all occurrences of a pattern in a text, after the text is preprocessed. In the dynamic text indexing problem, updates to the text in the form of insertions and deletions of substrings are permitted. The dictionary matching problem deals with finding all occurrences of each pattern set of a set of patterns in a text, after the pattern set is preprocessed. In the dynamic dictionary matching problem, insertions and deletions of patterns to the pattern set are permitted},
	keywords = {algorithm;replaced, algorithmics;substrings;suffix, algorithms;pattern, approximate, characters;dynamic, characters;labeling, characters;string, complexity;indexing;parallel, construction;computational, data, dictionary, dynamic, indexing;efficient, matching;deleted, matching;dynamic, matching;efficient, matching;inserted, matching;string, matching;tree, paradigm;optimal, Parallel, pattern, PROCESSING, string, structures;, text, tree},
	doi = {10.1109/SFCS.1996.548491},
	author = {Sahinalp,S. C and Vishkin, Uzi}
}
@conference {14955,
	title = {Efficient Algorithms for Atmospheric Correction of Remotely Sensed Data},
	booktitle = {Supercomputing, 1995. Proceedings of the IEEE/ACM SC95 Conference},
	year = {1995},
	month = {1995///},
	pages = {12 - 12},
	abstract = {Remotely sensed imagery has been used for developing and validating various studies regarding land cover dynamics. However, the large amounts of imagery collected by the satellites are largely contaminated by the effects of atmospheric particles. The objective of atmospheric correction is to retrieve the surface reflectance from remotely sensed imagery by removing the atmospheric effects. We introduce a number of computational techniques that lead to a substantial speedup of an atmospheric correction algorithm based on using look-up tables. Excluding I/O time, the previous known implementation processes one pixel at a time and requires about 2.63 seconds per pixel on a SPARC-10 machine, while our implementation is based on processing the whole image and takes about 4-20 microseconds per pixel on the same machine. We also develop a parallel version of our algorithm that is scalable in terms of both computation and I/O. Experimental results obtained show that a Thematic Mapper (TM) image (36 MB per band, 5 bands need to be corrected) can be handled in less than 4.3 minutes on a 32-node CM-5 machine, including I/O time.},
	keywords = {Atmospheric, AVHRR;, computing;, correction;, high, I/O;, Parallel, performance, processing;, remote, scalable, sensing;, TM;},
	doi = {10.1109/SUPERC.1995.242453},
	author = {Fallah-Adl,H. and JaJa, Joseph F. and Liang,Shunlin and Kaufman,Y.J. and Townshend,J.}
}
@article {15022,
	title = {Scalable data parallel algorithms for texture synthesis using Gibbs random fields},
	journal = {Image Processing, IEEE Transactions on},
	volume = {4},
	year = {1995},
	month = {1995/10//},
	pages = {1456 - 1460},
	abstract = {This article introduces scalable data parallel algorithms for image processing. Focusing on Gibbs and Markov random field model representation for textures, we present parallel algorithms for texture synthesis, compression, and maximum likelihood parameter estimation, currently implemented on Thinking Machines CM-2 and CM-5. The use of fine-grained, data parallel processing techniques yields real-time algorithms for texture synthesis and compression that are substantially faster than the previously known sequential implementations. Although current implementations are on Connection Machines, the methodology presented enables machine-independent scalable algorithms for a number of problems in image processing and analysis},
	keywords = {algorithms;maximum, algorithms;parallel, algorithms;scalable, algorithms;texture, analysis;image, CM-2;Thinking, CM-5;fine-grained, compression;image, compression;texture, Connection, data, estimation;model, estimation;parallel, field;Thinking, fields;Markov, likelihood, machine, Machines;Gibbs, machines;random, Parallel, parameter, processes;, processes;data, processing;image, processing;machine-independent, random, representation;real-time, scalable, synthesis;Markov, texture;maximum},
	isbn = {1057-7149},
	doi = {10.1109/83.465111},
	author = {Bader, D.A. and JaJa, Joseph F. and Chellapa, Rama}
}
@article {15374,
	title = {A parallel-in-time method for the transient simulation of SOI devices with drain current overshoots},
	journal = {Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on},
	volume = {13},
	year = {1994},
	month = {1994/08//},
	pages = {1035 - 1044},
	abstract = {This paper presents a new parallel-in-time algorithm for the two dimensional transient simulation of SOI devices. With this approach, simulation in both space and time domains is performed in parallel As a result, the CPU time is reduced significantly from the conventional serial-in-time method. This new approach fully exploits the inherent parallelism of the finite difference formulation of the basic semiconductor device equations and the massively parallel architecture of SIMD computers. The space domain computations are inherently parallel due to the nature of our technique of solving the finite-difference equations. Time domain parallelism is achieved by shifting the potentials from previous time points to subsequent points one-step forward along the time axis with each Gummel iteration. This algorithm employs a fixed-point iteration technique, therefore a direct solution of matrix equations is avoided. The algorithm is especially suitable for the transient simulation of SOI devices that exhibit transient drain current overshoot. Numerical experiments show that the new parallel-in-time method is up to eight times faster than the conventional serial-in-time method in SOI transient simulations. The program is coded in CM Fortran for the Connection Machine},
	keywords = {2D, algorithms;semiconductor, analysis;transient, architecture;parallel-in-time, boundaries;silicon;time-domain, computations;time, computers;SOI, computing;finite, current, device, devices;drain, devices;parallel, difference, dimensional, domain, effect, engineering, equations;fixed-point, equations;space, field, Fortran;CPU, gate, iteration, iteration;SIMD, Machine;Gummel, method;semiconductor, methods;insulated, methods;metal-insulator-semiconductor, models;semiconductor-insulator, overshoots;finite-difference, Parallel, parallelism;transient, response;, simulation;CM, simulation;digital, simulation;electronic, simulation;two, technique;massively, time;Connection, transistors;iterative},
	isbn = {0278-0070},
	doi = {10.1109/43.298039},
	author = {Tai,G.-C. and Korman,C.E. and Mayergoyz, Issak D}
}
@conference {14939,
	title = {An efficient parallel algorithm for channel routing},
	booktitle = {Computer Design: VLSI in Computers and Processors, 1990. ICCD {\textquoteright}90. Proceedings., 1990 IEEE International Conference on},
	year = {1990},
	month = {1990/09//},
	pages = {400 - 403},
	abstract = {The channel-routing of a set of multiterminal nets in the standard two-layer model is considered. The sequential algorithms based on the greedy strategy do not seem to be easily parallelizable. Proposed is an efficient parallel algorithm for routing channels with cyclic constraints. The algorithm runs in time <e1>O</e1>(<e1>n</e1><sup>2</sup>/<e1>p</e1>+log<sup>2</sup><e1>p</e1>), with <e1>p</e1> processors, on a shared memory parallel random access machine (PRAM) model where 1 les;<e1>p</e1> les;<e1>n</e1><sup>2</sup> radic; and <e1>n</e1> is the size of the input. An efficient adaptation of this algorithm on a Sequent Balance 21000 multiprocessor system is reported},
	keywords = {21000;channel, access, algorithm;sequential, algorithms;, algorithms;shared, balance, CAD;computational, complexity;parallel, Layout, machine;standard, memory, model;circuit, nets;parallel, Parallel, PRAM;Sequent, random, routing;multiprocessor, system;multiterminal, two-layer},
	doi = {10.1109/ICCD.1990.130261},
	author = {Krishnamurthy, S. and JaJa, Joseph F.}
}
