Newsgroups: comp.lang.scheme Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!hx.lcs.mit.edu!ziggy From: ziggy@hx.lcs.mit.edu (Michael R. Blair) Subject: Re: Fixing the order of evaluation. Message-ID: <1991Apr9.212135.17980@mintaka.lcs.mit.edu> Followup-To: ziggy@lcs.mit.edu Keywords: multi-processor, parallelism, concurrency Sender: news@mintaka.lcs.mit.edu Organization: MIT Laboratory for Computer Science Date: Tue, 9 Apr 91 21:21:35 GMT Lines: 82 In Scheme Digest Vol.3 No.178, Tim Moore writes: >Date: 5 Apr 91 16:36:03 GMT >From: Tim Moore >Organization: University of Utah CS Dept >In article jaffer writes: >>gjc and others suggest fixing the order of evaluation. If this order >>is fixed Scheme will lose the ability to be easily run on multiple >>processors. This will confine scheme to the dustbin of history. >> >As was pointed out earlier, the unspecified order of evaluation has >almost no effect, pro or con, on running Scheme on multi-processors. >Arguments can be evaluated in any order, but evaluation cannot be >interleaved. Uhm, be careful here... nothing was pointed out earlier, rather something was claimed but not demonstrated. Let me clarify why an unspecified order of evaluation *does* matter to multi-processor Scheme's. If the order is unspecified then any order may be chosen so long as it corresponds to some sequential evaluation of the arguments. The intersting case is when two (or more) arguments interfere in the sense that one alters a memory location which the other either reads or writes. If the evaluation order is unspecified then this permits non-determinism, which may well be desirable. Notice that this does *not* violate sequential semantics. Now, the important issue arises when one considers how to keep all the processors in the multi-processor Scheme busy most of the time. This is called ``load balancing''. Good load balancing ensures low latency. Now, consider the situation where all but a couple processors are busy when we encounter an application with multiple arguments. One of these arguments may require many resources to evaluate whereas the other requires few. If we imagine load balancing to be like playing Tetris, the prudent thing to do is to dedicate the few resources we have available to the evaluation of the argument which requires only a few. Imagine, for instance, that we have discovered at compile time or by post-mortem analysis of a prior invocation, that this produces good load balancing by virtue of having sneeked in a full argument eval where only a partial argument eval would otherwise have fit. Specifically, the argument which requires many resources may make only a little progress before blocking due to lack of available resources whereas the arg which requires only a little resources could fully evaluate with the available resources. In short, the less blocking incurred, the less the synchronization/communication overhead will dominate the computation so the more ``real'' work will get done. The important result of this proposed scenario is that if you fix the order of evaluation to disallow non-determinism in the argument evaluation then you would not permit multi-processor Scheme's to exhibit good load balancing in the face of non-determinism. Thus, in your desire to allow programmer's to write questionably more succinct code, code which actually obfuscates the control dependencies between code fragments, you will have relegated Scheme to inferior performance on multi-processor machines, in effect proclaiming Scheme to be a SERIAL language. I personally feel this would be a regrettable trade-off to have made because I personally believe in the virtues of non-determinism and speculative parallelism in multi-processing. (And I also personally feel it is counter-productive to engage in debate as to whether or not changing the language in certain ways would affect multi-processor implementations until I have become versed in the issues which arise in multi-processing implementations. Until that point, I typically phrase my postings as querys rather than as unfounded claims. Proof by lack of imagination is Modus Bogus... and is considered professionally embarassing in credible academic settings.) ------------------------------------------------------------------------------- ziggy@lcs.mit.edu Michael R. Blair MIT Laboratory for Confuser Science (617) 253-6833 [O] -. 545 Technology Square --- Room 437 (617) 577-1167 [H] /\. Cambridge, MA 02139 ------------------------------------------------------------------------------- -- ------------------------------------------------------------------------------- ziggy@lcs.mit.edu Michael R. Blair MIT Laboratory for Confuser Science (617) 253-6833 [O] -. 545 Technology Square --- Room 437 (617) 577-1167 [H] /\. Cambridge, MA 02139