Multy-core CPUs

>
> Deadlock can only happen if one process waits for another. E does
> *never* wait, there is no wait instruction. Instead, it schedules a
> message to be run when the desired computation completes. This leaves
> the Vat free to execute other messages in the meantime. In Croquet, this
> looks like here:
>
>    "future is Croquet's variant for sending async messages"
>    promise := rcvr future doSomething.
>    promise whenResolved:[:value|
>         "do something with the result of the computation
>           this block will executed once the concurrent computation
>          is completed and the response message is being processed
>          in this Vat/Island."
>    ].

> Because there is no wait, "classic deadlock" simply cannot happen. There
> is an equivalent situation which is called "data lock" where circular
> dependencies will cause a computation not to make progress (because a is
> computed in response to the completion of b, b in response to completion
> of c and c in response of completion of a). But there are *major*
> differences to deadlocks: First, datalock is deterministic, it only
> depends on the sequence of messages which can be examined. Second,
> because the Vat is *not* blocked, you are free to send further messages
> to resolve any one of the dependencies and continue making progress.
>
> In other words, the "control flow problem" of deadlock has been turned
> around into a "data flow problem" (promises and completion messages)
> with much less dramatic consequences when things go wrong.
>
> Cheers,
>    - Andreas

>
> On Oct 25, 2007, at 12:28 PM, Peter William Lount wrote:
>
> > The Tile-64 processor is expected to grow to about 4096 processors
> > by pushing the limits of technology beyond what they are today. To
> > reach the levels you are talking about for a current Smalltalk image
> > with millions of objects each having their own thread (or process)
> > isn't going to happen anytime soon.
> >
> > I work with real hardware.
>
>
> A couple of numbers:
>
> - Montecito, the new dual-core Itanic has 1.72 billion transistors.
> - The ARM6 macrocell has around 35000 transistors
> - divide the two, and you will find that you could get more ARM6 cores
> for the Montecito transistor budget than the ARM6 has transistors
>
> So we can have a 35K object system with every processor having its own
> CPU core and all message-passing being asynchronous.  This is likely
> to be highly inefficient, with most of the CPUs waiting/idle most of
> the time, say 99%.  With 1% efficiency, and say, a 200MHz clock, the
> effective throughput would still be 200M * 35000 / 100 =  70 billion
> instructions per second.  That's a lot of instructions.  And wait what
> happens if we have some really parallel algorithm that cranks
> efficiency up to 10%!
>
> I am not saying any of these numbers are valid or that this is a
> realistic system, but I do find the numbers of that little thought
> experiment...interesting.  And of coures, while Moore's law appears to
> have stoppe for cycle times, it does seem to still be going for
> transistors per chip.
>
> Marcel
>
>
>
>

> A couple of numbers:
>
> - Montecito, the new dual-core Itanic has 1.72 billion transistors.
> - The ARM6 macrocell has around 35000 transistors
> - divide the two, and you will find that you could get more
> ARM6 cores for the Montecito transistor budget than the ARM6
> has transistors
>
> So we can have a 35K object system with every processor
> having its own CPU core and all message-passing being
> asynchronous.  This is likely to be highly inefficient, with
> most of the CPUs waiting/idle most of the time, say 99%.  
> With 1% efficiency, and say, a 200MHz clock, the effective
> throughput would still be 200M * 35000 / 100 =  70 billion
> instructions per second.  That's a lot of instructions.  And
> wait what happens if we have some really parallel algorithm
> that cranks efficiency up to 10%!
>
> I am not saying any of these numbers are valid or that this
> is a realistic system, but I do find the numbers of that
> little thought experiment...interesting.  And of coures,
> while Moore's law appears to have stoppe for cycle times, it
> does seem to still be going for transistors per chip.
>
> Marcel
>
>
>

> Peter,
>
> I also want to thank you for this link:
> http://www.greenteapress.com/semaphores/downey05semaphores.pdf
> I started to read it after David's comment about it and it is
> entertaining and I am learning lots.
>
> I also plan on using it in phase 3 of my multi-threaded vm project.
>
> Phase 1, my current phase, is to get all msg sends to be interceptable
> by the SqueakElib promise framework.  This includes things that have
> been macro transformed by the Compiler, like #ifTrue:, #ifNil:,
> #whileTrue:, and so on. It also includes bytecodeMethods like #class
> and #==.
>
> Phase 2 is to allow all primitives and bytecode methods to have a
> promise as an argument.  Here, my plan is to stop short the primitive
> call and send the excapsulated primitive call to the promise(s) as
> part of a whenMoreResolved call.  When the promise resolves, the
> primitive call will be made.  QoS can be satisfied by joining the
> promise with a timer, such that if the promise does not resolve in xxx
> milliseconds, it will become broken and the primitive call will "fail".
>
> Phase 3 is to make the Interpreter multithreaded, while protecting
> ObjectMemory with Semaphores.  I have a quad-core chip and so I want 4
> Interpreter threads (Vats).  Only one of them can be inside of
> ObjectMemory at a time and that could be for purposes of allocation,
> mutation, or GC. It's possible that a simple mutex semaphore would
> suffice, initially.   In this model, references to objects in other
> Vats will be ThreadRefs (a form of a FarRef) and msgs will be
> serialized to the other Vat (reassigned the VatID in the same shared
> ObjectMemory, or copied to a different but co-located ObjectMemory).
>
> I don't think having a single ObjectMemory will scale to 10's of
> "processors", but will probably also need to be multithreaded with one
> per Vat.  It's good from the standpoint of no shared memory.  One
> challenge then is what if refs from 2 Vats are involved in the same
> primitive call.  Well, memory reads don't have to be protected, unless
> memory can be relocated, that is.  One thing at a time, I tell myself.
>
> I have 0 experience in this area (Interpreter+ObjectMemory), but I
> thought it would be fun.  Your link will help tremendously.
>
> Cheers,
> Rob
>
>

> -----Original Message-----
> From: Peter William Lount
>
> Rob Withers wrote:
> > Peter,
> >
> > I also want to thank you for this link:
> > http://www.greenteapress.com/semaphores/downey05semaphores.pdf
> > I started to read it after David's comment about it and it is
> > entertaining and I am learning lots.
> >
> > I also plan on using it in phase 3 of my multi-threaded vm project.
> >
> > Phase 1, my current phase, is to get all msg sends to be interceptable
> > by the SqueakElib promise framework.  This includes things that have
> > been macro transformed by the Compiler, like #ifTrue:, #ifNil:,
> > #whileTrue:, and so on. It also includes bytecodeMethods like #class
> > and #==.
> >
> > Phase 2 is to allow all primitives and bytecode methods to have a
> > promise as an argument.  Here, my plan is to stop short the primitive
> > call and send the excapsulated primitive call to the promise(s) as
> > part of a whenMoreResolved call.  When the promise resolves, the
> > primitive call will be made.  QoS can be satisfied by joining the
> > promise with a timer, such that if the promise does not resolve in xxx
> > milliseconds, it will become broken and the primitive call will "fail".
> >
> > Phase 3 is to make the Interpreter multithreaded, while protecting
> > ObjectMemory with Semaphores.  I have a quad-core chip and so I want 4
> > Interpreter threads (Vats).  Only one of them can be inside of
> > ObjectMemory at a time and that could be for purposes of allocation,
> > mutation, or GC. It's possible that a simple mutex semaphore would
> > suffice, initially.   In this model, references to objects in other
> > Vats will be ThreadRefs (a form of a FarRef) and msgs will be
> > serialized to the other Vat (reassigned the VatID in the same shared
> > ObjectMemory, or copied to a different but co-located ObjectMemory).
> >
> > I don't think having a single ObjectMemory will scale to 10's of
> > "processors", but will probably also need to be multithreaded with one
> > per Vat.  It's good from the standpoint of no shared memory.  One
> > challenge then is what if refs from 2 Vats are involved in the same
> > primitive call.  Well, memory reads don't have to be protected, unless
> > memory can be relocated, that is.  One thing at a time, I tell myself.
> >
> > I have 0 experience in this area (Interpreter+ObjectMemory), but I
> > thought it would be fun.  Your link will help tremendously.
> >
> > Cheers,
> > Rob
> >
> >
> Hi Rob,
>
> Yeah, it's an awesome little book that cuts right to the chase. I
> particularly like that they show some solutions that won't work as
> concurrency is quite difficult and sometimes you think it's correct when
> it isn't. It's good to learn about those pitfalls.
>
> You're plan sounds excellent. Thank you for taking up the task of making
> Squeak VM multi-threaded with native threads!
>
> If you need anything...
>
> All the best,
>
> Peter
>

>
> On 25-Oct-07, at 9:25 PM, Marcel Weiher wrote:
>>
>> - Montecito, the new dual-core Itanic has 1.72 billion transistors.
>> - The ARM6 macrocell has around 35000 transistors
>> - divide the two, and you will find that you could get more ARM6
>> cores for the Montecito transistor budget than the ARM6 has transistors
>
> Nicely pointed out Marcel! I've been trying to make a similar point
> for about, oh two decades now....
>
> In fact around ten years ago TI announced some new technology relating
> to wafer scale fabrication (I think, don't hold me to this) and as an
> illustration of its possibilities they said it meant they could put
> (something like) 128 StrongARM cpus each with 4MB ram on a wafer.  Now
> let's say we take an easy path and put a mere 1000 ARM cores on a
> chip, so as to leave some room for caches and transputer-like links (I
> think someone actually did those for ARM at some point in the past)
> and interface stuff. ARM 1176 cores are rated for 800MHz with claims
> of up to 1GHz so we have potential for a quadrillion instruction per
> second. Even Microsoft would surely have trouble soaking up that much
> cpu with pointless fiddle-faddle.
>
> If we got no better than 1% useful work because of poor code we'd
> still be getting 10 gips.

> On 10/24/07, Sebastian Sastre <[hidden email]> wrote:
> >
> > So I'm stating here that in a smalltalk image of the future *every object
> > should have a process*. Every instance. All of them.
>
> That is an interesting idea.  That would open a door to a new way of
> Garbage collection, because it can then be tied to the exit of a
> process.
>
> > Said that I return to the problem you stated about the need of copy copy
> > copy, saying that this premise changes things and you don't need to copy
> > anymore because a VM like that, no matter who or when, an instVar of an
> > object is to be modified it will provide you of guarantee that the write
> > will be made by the process that corresponds to that instance.
>
> Yes, in such a system, you don't need to copy because all that gets
> passed around are references to processes.
>
>

>
>  Jason Johnson wrote:
>  On 10/26/07, Peter William Lount <[hidden email]> wrote:
>
>
>  You're plan sounds excellent. Thank you for taking up the task of making
> Squeak VM multi-threaded with native threads!
>
>  Yes, thanks. I will need a true mult-threaded VM at some point as
> well. I just have to make it transparent to the processes running in
> the VM. :)
>
>
>  Hi,
>
>  I really do like the notion of easy multi threading - really. I've admired
> Erlang for what it's achieved in that regard for years now. I encourage
> everyone interested in that to keep persevering and searching for a
> practical way forward towards your vision.
>
>  All the best,
>
>  Peter
>
>
>
>
>