MULTIPROCESSOR SIMULATION STRATEGIES WITH OPTIMAL SPEED-UP

Authors
DUNNE PE GITTINGS CJ LENG PH
Citation
Pe. Dunne et al., MULTIPROCESSOR SIMULATION STRATEGIES WITH OPTIMAL SPEED-UP, Information processing letters, 54(1), 1995, pp. 23-33
Citations number
18
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
54
Issue
1
Year of publication
1995
Pages
23 - 33
Database
ISI
SICI code
0020-0190(1995)54:1<23:MSSWOS>2.0.ZU;2-4
Abstract
In this paper we consider 2-processor algorithms for simulating the be haviour of given formulae over the basis {+}, where + denotes the two argument Boolean function, Exclusive-Or. A sequence of 2-processor sim ulation strategies [S-r] (r greater than or equal to 0) is described a nd it is proved that the ratio ex(r)[n]/n approach 0.5, where ex(r)[n] is the expected number of steps taken by S-r on n-node formulae gener ated at random using the binary search tree distribution.