Several Not So Recent Technical Reports Available for Download


Please see the Explicit Multi-Threading (XMT) home page for some more recent papers.

Class notes on parallel algorithms

  • U. Vishkin. Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages. These class notes are meant to make the fundamental theory of parallel algorithms accessible to computer science and engineering graduate students. They have also been tested successfully for upper division undergraduate students.
    Download class notes.

    Parallel algorithms

  • O. Berkman, B. Schieber and U. Vishkin. Optimal doubly logarithmic optimal parallel algorithms based on finding all nearest smaller values. J. of Algorithms 14 (1993) 344-370.
    Download TR (sorry, but figures are not included!).
  • O. Berkman, B. Schieber and U. Vishkin. A fast parallel algorithm for finding the convex hull of a sorted point set. International Journal of Computational Geometry and Applications, 6 (1996), 231-241.
    Download TR.
  • S. C. Sahinalp and U. Vishkin. Symmetry breaking for suffix tree construction. In Proc. 26th Annual ACM Symp. on Theory of Computing, 1994, 300-309.
    Download TR.
    Pointer to talk.
  • S. C. Sahinalp and U. Vishkin. Efficient approximate and dynamic matching of patterns using a labeling paradigm. In Proc. 37th Annual IEEE Symposium on Foundations of Computer Science, 1996. Download TR.
  • R. Raman and U. Vishkin. Parallel algorithms for database operations and a database operation for parallel algorithms. In Proc. 9th IEEE International Parallel Processing Symposium (IPPS), 1995.
    Download TR.
  • S. Khuller, U. Vishkin and N. Young. A primal-dual parallel approximation technique applied to weighted set and vertex cover. J. Algorithms, 17,2 (1994), 280-289.
    Download TR.
  • Y. Matias and U. Vishkin. On parallel hashing and integer sorting. J. of Algorithms 12,4 (1991) 573-606.
    Download TR.
  • O. Berkman, Y. Matias and U. Vishkin. Randomized Range-Maxima in Nearly-Constant Parallel Time. Computational Complexity 2 (1992) 350-373.
    Download TR.
  • Y. Matias and U. Vishkin. On integer sorting and parallel hashing. In Proc. 17th ICALP, Lecture Notes in Computer Science, Vol. 443, Springer-Verlag, 1990, 729-743.
  • Y. Matias and U. Vishkin. Converting high probability into nearly-constant time - with applications to parallel hashing. In Proc. 23rd Annual ACM Symp. on Theory of Computing, 1991, 307-316.
    Download TR.
  • J. Gil, Y. Matias and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, 698-710.
    Download TR.
  • M.T. Goodrich, Y. Matias and U. Vishkin. Approximate parallel prefix computation and its Applications. In Proc. 7th IEEE International Parallel Processing Symposium (IPPS), 1993, 318-325. Download TR.
  • M.T. Goodrich, Y. Matias and U. Vishkin. Optimal parallel approximation algorithms for prefix sums and integer sorting. In Proc. Fifth Annual ACM-SIAM Symp. on Discrete Algorithms, 1994, 241-250.
    Download TR.
  • Y. Matias and U. Vishkin. A note on reducing parallel model simulations to integer sorting. In Proc. 9th IEEE International Parallel Processing Symposium (IPPS), 1995.
    Download TR.

    Lower bounds for low bandwidth parallel computing

  • Y. Mansour, N. Nisan, and U. Vishkin. Trade-offs between communication throughput and parallel time. In Proc. 26th Annual ACM Symp. on Theory of Computing, 1994, 372-381. Also, to appear in Journal of Complexity (Special Edition in Honor of Zvi Galil's 50th Birthday).
    Download TR.
    Postscript comment. In August 1998, the U.S. President's Information Technology Advisory Committee (PITAC) wrote, ``There is substantive evidence that current scalable parallel architectures are not well suited for a number of important applications, especially those where the computations are highly irregular or those where huge quantities of data must be transferred from memory to support the calculation''. In our opinion, the current theoretical paper, whose conference version appeared in the 1994 ACM-STOC, anticipated these limitations of current parallel architectures (and the implied need for new computation frameworks).

    Parallel complexity

  • S. Khuller and U. Vishkin. On the parallel complexity of digraph reachability. Information Processing Letters, 52,5 (1994), 239-242.
    Download TR.

    Principles for uniprocessor, or unichip-centered, parallel computing

  • Please see the Explicit Multi-Threading (XMT) home page for more recent papers.
  • U. Vishkin, S. Dascal, E. Berkovich and J. Nuzman. Explicit Multi-Threading (XMT) Bridging Models for Instruction Parallelism. In Proc. 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1998.
    Download TR.
    The XMT home page.
  • U. Vishkin. Can parallel algorithms enhance serial implementation? In Proc. 8th IEEE International Parallel Processing Symposium (IPPS), 1994, 376-385.
    Download TR.
  • S.M. Mueller and U. Vishkin. Conflict-Free Access to Multiple Single-Ported Register Files. In Proc. 11th IEEE International Parallel Processing Symposium (IPPS), 1997.
    Download TR.
  • U. Vishkin. From algorithm parallelism to instruction-level parallelism: an encode-decode chain using prefix-sum. In Proc. 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1997.
    Download abstract.
    Download TR.
    Download an earlier TR (which INCLUDES a full breadth-first search example).
    Download talk.
  • R. Orny and U. Vishkin. Two computer systems paradoxes: serialize-to-parallelize, and queuing concurrent-writes, UMIACS-TR-96-1, University of Maryland Institute for Advanced Computer Studies, College Park, MD 20742-3251, September 1995.
    Download TR.

    Parallel computing: survey, position paper and position solicitation paper

  • U. Vishkin. Structural parallel algorithmics. In Proc. 18th ICALP, Lecture Notes in Computer Science, Vol. 510 Springer-Verlag, 1991, 363-380.
    Download TR. The original publication is available at www.springerlink.com
  • U. Vishkin. A case for the PRAM as a standard programmer's model. In Proc. Workshop on Parallel Architectures and Their Efficient Use: State of the Art and Perspectives, First Heinz-Nixdorf Symposium, Paderborn, Germany, November 11 - 13, 1992, Lecture Notes in Computer Science, Volume 678, 1993, 11-19.
    Download TR.
  • U. Vishkin. Suggesting computer science agenda(s) for High-Performance Computing: an introduction. In U. Vishkin (editor), Developing a Computer Science Agenda for High-Performance Computing, ACM Press, 1994, 158 pages.
    Download TR.

    Pattern matching

  • G.M. Landau and U. Vishkin. Pattern matching in a digitized image. Algorithmica, 12,4/5 (1994), 375-408.
    Download TR.
  • S. C. Sahinalp and U. Vishkin. Symmetry breaking for suffix tree construction. In Proc. 26th Annual ACM Symp. on Theory of Computing, 1994, 300-309.
    Download TR.
    Pointer to talk.
  • S. C. Sahinalp and U. Vishkin. Efficient approximate and dynamic matching of patterns using a labeling paradigm. In Proc. 37th Annual IEEE Symposium on Foundations of Computer Science, 1996. Download TR.
  • S. C. Sahinalp and U. Vishkin. Approximate pattern matching using locally consistent parsing. Submission for journal publication, 1997. Download TR.

    More algorithms

  • S. Khuller and U. Vishkin. Biconnectivity approximations and graph carvings. JACM 41,2 (1994), 214-235.
    Download TR.
  • R. Cole and U. Vishkin. On the detection of robust curves. Computer Vision, Graphics, and Image Processing (CVGIP): Graphical Download TR.
  • S. Kutten, D. Peleg and U. Vishkin. Deterministic resource discovery in distributed networks. In Proc. 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2001.
    Download TR.