%0 Conference Paper %B Computer Design, 2009. ICCD 2009. IEEE International Conference on %D 2009 %T Algorithmic approach to designing an easy-to-program system: Can it lead to a HW-enhanced programmer's workflow add-on? %A Vishkin, Uzi %K abstraction;PRAM-On-Chip;easy-to-program %K algorithms;parallel %K algorithms;sorting; %K designing;explicit %K multi-threading;fine-grained %K PRAM %K random-access-machine/model;parallel %K sorting %K system %K system;parallel %K systems;concurrency %K THEORY %K theory;multi-threading;parallel %K threads;many-core %X Our earlier parallel algorithmics work on the parallel random-access-machine/model (PRAM) computation model led us to a PRAM-On-Chip vision: a comprehensive many-core system that can look to the programmer like the abstract PRAM model. We introduced the eXplicit MultiThreaded (XMT) design and prototyped it in hardware and software. XMT comprises a programmer's workflow that advances from work-depth, a standard PRAM theory abstraction, to an XMT program, and, if desired, to its performance tuning. XMT provides strong performance for programs developed this way due to its hardware support of very fine-grained threads and the overhead of handling them. XMT has also shown unique promise when it comes to ease-of-programming, the biggest problem that has limited the impact of all parallel systems to date. For example, teachability of XMT programming has been demonstrated at various levels from rising 6th graders to graduate students, and students in a freshman class were able to program 3 parallel sorting algorithms. The main purpose of the current paper is to stimulate discussion on the following somewhat open-ended question. Now that we made significant progress on a system devoted to supporting PRAM-like programming, is it possible to incorporate our hardware support as an add-on into other current and future many-core systems? The paper considers a concrete proposal for doing that: recasting our work as a hardware-enhanced programmer's workflow ¿module¿ that can then be essentially imported into the other systems. %B Computer Design, 2009. ICCD 2009. IEEE International Conference on %P 60 - 63 %8 2009/10// %G eng %R 10.1109/ICCD.2009.5413174 %0 Conference Paper %B Foundations of Computer Science, Annual IEEE Symposium on %D 1995 %T Transforming men into mice (polynomial algorithm for genomic distance problem) %A Hannenhalli, Sridhar %A Pevzner,P.A. %K biology computing %K combinatorial properties %K comparative physical mapping data %K computable parameters %K duality (mathematics) %K duality theorem %K evolution (biological) %K Genetics %K genome rearrangement algorithm %K genomic distance problem %K genomic rearrangements %K human-mouse evolution %K mammalian evolution %K multi chromosomal genomes %K parsimonious rearrangement scenarios %K pattern matching %K polynomial algorithm %K polynomial time algorithm %K set theory %K sorting %K string matching %K strings %K zoo fish %X Many people believe that transformations of humans into mice happen only in fairy tales. However, despite some differences in appearance and habits, men and mice are genetically very similar. In the pioneering paper, J.H. Nadeau and B.A. Taylor (1984) estimated that surprisingly few genomic rearrangements (178/spl plusmn/39) happened since the divergence of human and mouse 80 million years ago. However, their analysis is nonconstructive and no rearrangement scenario for human-mouse evolution has been suggested yet. The problem is complicated by the fact that rearrangements in multi chromosomal genomes include inversions, translocations, fusions and fissions of chromosomes, a rather complex set of operations. As a result, at first glance, a polynomial algorithm for the genomic distance problem with all these operations looks almost as improbable as the transformation of a (real) man into a (real) mouse. We prove a duality theorem which expresses the genomic distance in terms of easily computable parameters reflecting different combinatorial properties of sets of strings. This theorem leads to a polynomial time algorithm for computing most parsimonious rearrangement scenarios. Based on this result and the latest comparative physical mapping data we have constructed a scenario of human-mouse evolution with 131 reversals/translocaitons/fusions/fissions. A combination of the genome rearrangement algorithm with the recently proposed experimental technique called ZOO FISH suggests a new constructive approach to the 100 year old problem of reconstructing mammalian evolution. %B Foundations of Computer Science, Annual IEEE Symposium on %I IEEE Computer Society %C Los Alamitos, CA, USA %P 581 - 581 %8 1995/// %G eng %R http://doi.ieeecomputersociety.org/10.1109/SFCS.1995.492588 %0 Conference Paper %B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93 %D 1993 %T A distributed algorithm for ear decomposition %A Hannenhalli, Sridhar %A Perumalla,K. %A Chandrasekharan,N. %A Sridhar,R. %K Asynchronous communication %K asynchronous communication network %K Automata %K Communication networks %K computational complexity %K Computer networks %K Computer science %K decomposition graph %K distributed algorithm %K distributed algorithms %K Distributed computing %K Ear %K ear decomposition %K graph theory %K message-optimal %K network decomposition %K sorting %K Testing %K time-optimal %X A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition %B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93 %I IEEE %P 180 - 184 %8 1993/05/27/29 %@ 0-8186-4212-2 %G eng %R 10.1109/ICCI.1993.315382 %0 Conference Paper %B , Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991 %D 1991 %T Parallel transitive closure computations using topological sort %A Hua,K. A %A Hannenhalli, Sridhar %K Computer science %K Concurrent computing %K data partitioning %K Database systems %K database theory %K deductive databases %K File systems %K horizontal partitioning %K joins %K local data fragments %K message passing multiprocessor system %K Multiprocessing systems %K Parallel algorithms %K PARALLEL PROCESSING %K parallel programming %K parallel transitive closure %K processing nodes %K relation tuples %K Relational databases %K sorting %K topological sort %X Deals with parallel transitive closure computations. The sort-based approaches introduced sorts the tuples of the relation into topological order, and the sorted relation is then horizontally partitioned and distributed across several processing nodes of a message passing multiprocessor system. This data partitioning strategy allows the transitive closure computation of the local data fragments to be computed in parallel with no interprocessor communication. The construction of the final result then requires only a small number of joins. Extensive analytical results are included in the paper as well. They show that the proposed techniques leads to a speedup that is essentially linear with the number of processors. Its performance is significantly better than the recently published hashless parallel algorithm %B , Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991 %I IEEE %P 122 - 129 %8 1991/12/04/6 %@ 0-8186-2295-4 %G eng %R 10.1109/PDIS.1991.183079 %0 Journal Article %J IEEE Transactions on Computers %D 1986 %T A Special-Function Unit for Sorting and Sort-Based Database Operations %A Raschid, Louiqa %A Fei,T. %A Lam,H. %A Su,S. Y.W %K Application software %K Computer applications %K Database machines %K Hardware %K hardware sorter %K Microelectronics %K Software algorithms %K Software design %K Software systems %K sort-based algorithms for database operations %K sorting %K special-function processor %K Technology management %X Achieving efficiency in database management functions is a fundamental problem underlying many computer applications. Efficiency is difficult to achieve using the traditional general-purpose von Neumann processors. Recent advances in microelectronic technologies have prompted many new research activities in the design, implementation, and application of database machines which are tailored for processing database management functions. To build an efficient system, the software algorithms designed for this type of system need to be tailored to take advantage of the hardware characteristics of these machines. Furthermore, special hardware units should be used, if they are cost- effective, to execute or to assist the execution of these software algorithms. %B IEEE Transactions on Computers %V C-35 %P 1071 - 1077 %8 1986/12// %@ 0018-9340 %G eng %N 12 %R 10.1109/TC.1986.1676715