{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T14:10:27Z","timestamp":1723126227252},"reference-count":0,"publisher":"Wiley","issue":"3-4","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Scientific Programming"],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>This paper demonstrates that significant improvements to automatic parallelization technology require that existing systems be extended in two ways: (1) they must combine high\u2010quality compile\u2010time analysis with low\u2010cost run\u2010time testing; and (2) they must take control flow into account during analysis. We support this claim with the results of an experiment that measures the safety of parallelization at run time for loops left unparallelized by the Stanford SUIF compiler\u2019s automatic parallelization system. We present results of measurements on programs from two benchmark suites \u2013 S<jats:sc>PECFP95<\/jats:sc> and N<jats:sc>AS<\/jats:sc> sample benchmarks \u2013 which identify inherently parallel loops in these programs that are missed by the compiler. We characterize remaining parallelization opportunities, and find that most of the loops require run\u2010time testing, analysis of control flow, or some combination of the two. We present a new compile\u2010time analysis technique that can be used to parallelize most of these remaining loops. This technique is designed to not only improve the results of compile\u2010time parallelization, but also to produce low\u2010cost, directed run\u2010time tests that allow the system to defer binding of parallelization until run\u2010time when safety cannot be proven statically. We call this approach <jats:italic>predicated array data\u2010flow analysis<\/jats:italic>. We augment array data\u2010flow analysis, which the compiler uses to identify independent and privatizable arrays, by associating predicates with array data\u2010flow values. Predicated array data\u2010flow analysis allows the compiler to derive \u201coptimistic\u201d data\u2010flow values guarded by predicates; these predicates can be used to derive a run\u2010time test guaranteeing the safety of parallelization.<\/jats:p>","DOI":"10.1155\/1999\/490628","type":"journal-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T14:09:40Z","timestamp":1421071780000},"page":"247-260","source":"Crossref","is-referenced-by-count":0,"title":["Combining Compile\u2010Time and Run\u2010Time Parallelization"],"prefix":"10.1155","volume":"7","author":[{"given":"Sungdo","family":"Moon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Byoungro","family":"So","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mary W.","family":"Hall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[1999,1]]},"container-title":["Scientific Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/1999\/490628.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1999\/490628","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T13:53:42Z","timestamp":1723125222000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1999\/490628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":0,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1155\/1999\/490628"],"URL":"https:\/\/doi.org\/10.1155\/1999\/490628","archive":["Portico"],"relation":{},"ISSN":["1058-9244","1875-919X"],"issn-type":[{"type":"print","value":"1058-9244"},{"type":"electronic","value":"1875-919X"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}