Path: utzoo!utgpu!watmath!att!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!ginosko!uunet!mcvax!ukc!harrier.ukc.ac.uk!gjap From: gjap@ukc.ac.uk (G.J.A.Paul) Newsgroups: comp.sys.transputer Subject: Re: choosing parallel languages Message-ID: <1981@harrier.ukc.ac.uk> Date: 7 Aug 89 11:01:23 GMT References: <8908011650.AA12679@kanga.cs.umass.edu.edu> <5726@pt.cs.cmu.edu> <1948@harrier.ukc.ac.uk> <5751@pt.cs.cmu.edu> Reply-To: gjap@ukc.ac.uk (G.J.A.Paul) Organization: Computing Lab, University of Kent at Canterbury, UK. Lines: 159 In article <5751@pt.cs.cmu.edu> jps@cat.cmu.edu (James Salsman) writes: >In article <1948@harrier.ukc.ac.uk> arc1@ukc.ac.uk (A.R.Curtis) writes: > >> occam has compile-time allocated memory. It deals solely with *real* >> memory, and none of this nice run-time virtual memory. > >By "virtual memory" do you mean "allocatable heap storage" >or "memory paged out to disk"? Occam can do both. A >Transputer OS should provide a process for these functions. > By "virtual memory", *I* would mean "as much memory as my process requires, even if this is more than is physically attached to the processor". I, for one, would be interested in seeing how you would implement paged memory on a processor without an MMU in any way, shape or form. By "Transputer OS", I presume you mean a glorified loader, like CP/M or MS/DOS, which falls over when the user process falls over. >> [In reply to the idea of using process abstraction for an >> "allocation server" -jps] >> Ok, so how do you provide a memory allocation server to handle >> completely arbitrary types? You can't, can you? But I can do this in >> C, can't I? > >I can tell that you aren't an Occam programmer because you >don't know about CHAN OF ANY and PORT OF ANY -- these >protocols map everything back and forth into BYTEs. CHAN OF ANY does not "map everything back and forth into BYTEs". It's just a method of switching off the compiler's checking on the types of data sent over a channel. You can (probably) get away with treating it as a CHAN OF BYTE over a physical link, but over a soft channel, all sorts of things at the implementation level (such as block copies) mean that this just doesn't work. This is not a problem with the implementation of soft channels -- semantically there is no obligation for this to work. Treat CHAN OF ANY as a bag on the side, there to allow easier conversion of occam 1. In those days, all you had was a CHAN, and you sent an integer tag to indicate what was coming next. Now we have tagged protocols to take care of that sort of thing for us, and check for silly errors too, we don't need to resort to this low level. (Aside: I happen to know that Tony has been programming in occam since the occam 1 days. He certainly has heard of CHAN OF ANY.) >> [Tony made some comments about having to allocate all memory >> at compile time] > >Every heap must be allocated some time. With Occam, you can >place your allocation process on a transputer that's next to >a disk (for swapping) or you can have a network of heap >processes, one on each processor. In that sort of a system >you can have a huge virtual address space with a distributed >index. Overflowed heap proceses can store on nearby >processors, and the "load" can be balanced or optimized >concurrently with the client processes. Ah, by swapping, you meant moving unused bits of heap away. You certainly can do this, but you write the code to do it. What I want is to be able to run arbitrary-sized programs on processors with finite amounts of memory. This might mean swapping some of the code out as well. Not so easy. On machines which support paging and swapping, this sort of support is built into the operating system. (On future Transputers, it might be built into the chip.) It certainly isn't, and can't ever be, part of a programming language. The whole point is to hide such mechanisms from the programmer. Going back to the heap allocation problem, Tony was right when he said that you couldn't do it generally. There are two cases; single processor, and multiple processor: (1) You place the heap in the memory of the process that is using it, and use sequential routines called from the user process to manage it. In this case the heap management package consists of routines to allocate and free blocks from a large array. The array is passed to the heap routines so it can write information into it about block sizes and utilisation. So, your routine asks the heap manager for a block of a certain size, it returns an index into the array, and you RETYPE the array FROM that index FOR the size for the object you wish to put into the heap. However, beware, because RETYPE will cause a run-time error if you don't have the alignment right. You can't check for alignment -- that's a low-level detail unconnected with occam semantics. Possibly this alignment problem is an implementation problem with the current compiler. The best bet is probably to use an array of INTs because they're what the processor deals with best (in occam 1 it's all you had :-). But remember the size of an INT is processor dependent, not an absolute value, so don't insert any magic numbers in your code when you're trying to work out how much heap space you will need for, say, an array of BYTEs. None of this is very elegant. Each process therefore has its own heap, allocated at compile time. The advantage of having a heap is that you don't have to make decisions about the balance of memory utilisation between processes until run-time (when they are made for you by the inputs to the task). If each process has its own heap then this automatic balancing is lost, and the overhead of a heap is wasted -- just give each process a fixed-size array (this is what you are effectively doing). Actually, the heap could be shared between processes on the same processor, and requests for part of it communicated to a heap management process; the manager could return an index into the array. However, this isn't occam. It isn't possible to check statically that processes are not accessing memory outside their allotted areas, i.e. usage checking would have to be turned off at compile time. (2) For the multiple processor case, a memory server processor could be implemented. In this case, you add data to the heap, and collect data from it via communication over channels. You'll need a tagged protocol with tags for all of the different types of object you will want to put in the heap. All reads and writes require the overhead of channel communication, and the heap manager needs database management capabilities (to avoid problems caused by parallel updates, if more than one process uses the heap). However, because the tags are application dependent, you need to write a dedicated memory-server for each application. Not a general solution. >It's hard for me to believe that you haven't heard of the >ANY protocol. Why do you post if you don't know what you're >talking about? > >:James P. Salsman (jps@CAT.CMU.EDU) He does know what he's talking about, it's just that he's not prepared to make the compromises and take the short cuts you suggest when writing programs. Don't use CHAN OF ANY because you are too lazy to define a tagged protocol. It is interesting to note that Geraint Jones' and Michael Goldsmith's book, "Programming in occam 2" devotes about half a page to CHAN OF ANY (it has over 300 pages in total), and it says (page 59) "... the only circumstance in which internal anarchic channels are reasonable is when simulating a piece of hardware for testing the process which will drive it." The INMOS "occam 2 Reference Manual" takes a similar line -- it talks about communication with an "alien process". Its description of the retyping is only valid for physical links. There are a lot of problems still to be solved in this area, and we need semantically secure solutions. However, it is good to see some support for occam from the other side of the Atlantic! Godfrey Paul