<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//TaxonX//DTD Taxonomic Treatment Publishing DTD v0 20100105//EN" "../../nlm/tax-treatment-NS0.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:tp="http://www.plazi.org/taxpub" article-type="research-article" dtd-version="3.0" xml:lang="en">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">109</journal-id>
      <journal-id journal-id-type="index">urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891</journal-id>
      <journal-title-group>
        <journal-title xml:lang="en">JUCS - Journal of Universal Computer Science</journal-title>
        <abbrev-journal-title xml:lang="en">jucs</abbrev-journal-title>
      </journal-title-group>
      <issn pub-type="ppub">0948-695X</issn>
      <issn pub-type="epub">0948-6968</issn>
      <publisher>
        <publisher-name>Journal of Universal Computer Science</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.3217/jucs-004-08-0675</article-id>
      <article-id pub-id-type="publisher-id">27508</article-id>
      <article-categories>
        <subj-group subj-group-type="heading">
          <subject>Research Article</subject>
        </subj-group>
        <subj-group subj-group-type="scientific_subject">
          <subject>C.1.2 - Multiple Data Stream Architectures (Multiprocessors)</subject>
          <subject>C.2 - COMPUTER-COMMUNICATION NETWORKS</subject>
          <subject>C.5 - COMPUTER SYSTEM IMPLEMENTATION</subject>
          <subject>F.1 - COMPUTATION BY ABSTRACT DEVICES</subject>
          <subject>F.2 - ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY</subject>
          <subject>G.3 - PROBABILITY AND STATISTICS</subject>
        </subj-group>
      </article-categories>
      <title-group>
        <article-title>Balanced PRAM Simulations via Moving Threads and Hashing</article-title>
      </title-group>
      <contrib-group content-type="authors">
        <contrib contrib-type="author" corresp="yes">
          <name name-style="western">
            <surname>Leppänen</surname>
            <given-names>Ville</given-names>
          </name>
          <email xlink:type="simple">ville.leppanen@cs.utu.fi</email>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
      </contrib-group>
      <aff id="A1">
        <label>1</label>
        <addr-line content-type="verbatim">Department of Computer Science, University of Turku, , Finland</addr-line>
        <institution>Department of Computer Science, University of Turku</institution>
        <country>Finland</country>
      </aff>
      <author-notes>
        <fn fn-type="corresp">
          <p>Corresponding author: Ville Leppänen (<email xlink:type="simple">ville.leppanen@cs.utu.fi</email>).</p>
        </fn>
        <fn fn-type="edited-by">
          <p>Academic editor: </p>
        </fn>
      </author-notes>
      <pub-date pub-type="collection">
        <year>1998</year>
      </pub-date>
      <pub-date pub-type="epub">
        <day>28</day>
        <month>08</month>
        <year>1998</year>
      </pub-date>
      <volume>4</volume>
      <issue>8</issue>
      <fpage>675</fpage>
      <lpage>689</lpage>
      <uri content-type="arpha" xlink:href="http://openbiodiv.net/D17A6D19-D072-5F12-A0BE-447515BA1ADD">D17A6D19-D072-5F12-A0BE-447515BA1ADD</uri>
      <uri content-type="zenodo_dep_id" xlink:href="https://zenodo.org/record/6995594">6995594</uri>
      <permissions>
        <copyright-statement>Ville Leppänen</copyright-statement>
        <license license-type="creative-commons-attribution" xlink:href="" xlink:type="simple">
          <license-p>This article is freely available under the J.UCS Open Content License.</license-p>
        </license>
      </permissions>
      <abstract>
        <label>Abstract</label>
        <p>We present a novel approach to parallel computing, where (virtual) PRAM processors are represented as light-weight threads, and each physical processor is capable of managing several threads. Instead of moving read and write requests, and replies between processor&amp;memory pairs (and caches), we move the light-weight threads. Consequently, the processor load balancing problem reduces to the problem of producing evenly distributed memory references. In PRAM computations, this can be achieved by properly hashing the shared memory into the processor&amp;memory pairs. We describe the idea of moving threads, and show that the moving threads framework provides a natural validation for Brent's theorem in work-optimal PRAM simulation situations on mesh of trees, coated mesh, and OCPC based distributed memory machines (DMMs). We prove that an EREW PRAM computation  requiring work W and time T, can be implemented work-optimally on those p-processor DMMs with high probability, if W = , where D is the diameter of the underlying routing machinery. The computation is work-optimal regardless how (virtual) PRAM processors terminate or initiate new PRAM processors during the computation. Our result is based on using only one randomly chosen hash function and on showing, how the threads (PRAM processors) can spawn new threads in required time on p-processor OCPC, 2-dimensional mesh of trees, 2-dimensional coated, and 3-dimensional coated mesh. A deterministic spawning algorithm is provided for all cases, although a randomized algorithm would be sufficient due to the randomized nature of time-processor optimal PRAM simulations.</p>
      </abstract>
    </article-meta>
  </front>
</article>
