dcsimg
A Flash Developer Resource Site

Results 1 to 10 of 10

Thread: [SHOW] Software Threads

  1. #1
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246

    [SHOW] Software Threads

    I've been working on implementing a software threading framework for as3. The idea, since we're constrained to a single thread for our ActionScript, is to break apart processes, and allow them to be run in the background; ideally without disrupting the game/application/whatever.

    The 2 things that first came to mind are what are in the demos. First was encoding a large (or many, or both!) images and the second was pathfinding. Both of these can totally lock up the player. You can see that in both cases the UI will totally freeze when executing linearly in one go on one frame, whereas the (admittedly slower) "green" thread method, does a fair job of keeping things responsive.

    image encoding demo: http://lab.generalrelativity.org/thr...imageEncoding/

    pathfinding demo:
    http://lab.generalrelativity.org/threading/pathfinding/

    In the image encoding demo, I'm encoding that same image 3 times in both cases. You can see, with the little diagnostic graphs, allocation opening up in the thread as other processes complete.

    The API is pretty straightforward, you implement a simple interface that allows your process (usually a chunk of an algorithm) to be run. Then you create a thread and pass it a list of all processes to execute, a frequency and a percentage share of the processor. The thread will do its best to maintain the framerate by allocating only the constrained amount of time and policing misbehaving processes. Threads can yield to allow for other heavy-processing to take precedence and then pick back up right where they left off.

    A verbose use of the framework would be:
    Code:
    //create the processes to execute
    var process1:IRunnable = new SomeProcess();
    var process2:IRunnable = new SomeOtherProcess();
    
    //wrap them in an array to pass to the thread
    var processes:Vector.<IRunnable> = Vector.<IRunnable>( [ process1, process2 ] );
    
    //define frequency
    var hertz:Number = stage.frameRate;
    
    //allow the thread to occupy whatever percentage of player's processing
    var share:Number = 0.3;
    
    //create the thread
    var thread:GreenThread = new GreenThread( processes, hertz, share );
    
    //listen for process and thread complete events
    thread.addEventListener( GreenThreadEvent.PROCESS_COMPLETE, processCompleteHandler );
    thread.addEventListener( Event.COMPLETE, threadCompleteHandler );
    
    //open the thread
    thread.open();
    But there are also utility methods to shorthand some of this:
    Code:
    ThreadUtil.openSingle( myProcess, callbackMethod );
    I have some more work on it still, but will be releasing it shortly to anyone interested.
    Last edited by newblack; 11-16-2008 at 04:06 AM.

  2. #2
    Senior Member Sietjp's Avatar
    Join Date
    Jan 2005
    Location
    Paris, France
    Posts
    709
    This is awsome. It seems it's not compatible with FP9, why ?

    Let's say I want to precompute a couple of things in background before starting a game. The precompute method is of this kind :
    PHP Code:
    for (var i:int=0;i<1000000;i++){
    //very heavy computations

    How do I turn this into a thread ?

  3. #3
    Student
    Join Date
    Apr 2001
    Location
    -
    Posts
    4,756
    the idea is interesting, the demos did not convinced me yet so far as there were still some minor hick ups esspecially at the beginning on older computers here- but I think the idea is very interesting.

    I remember flash pathfinding demos (flash 5 days) from the past that devided A* operations into smaler elements so that it could be spanned over a frame event and take on each cycle little resources, so instead of using loops each iteration would take place once per frame event.

    If I am not mistaken similar mechanics are used in realtime strategy games were complex pathfinding and resource simulation is handled into tiny pieces aside the engine execution.

  4. #4
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    @Sietjp: Yeah, I forgot to mention it's FP10. Sorry!
    So it would be really simple to turn that into a thread. You'd create a class that implements 2 methods and that stores a reference to the index (i).

    Code:
    public class HeavyComputer extends AbstractProcess implements IRunnable
    {
    
       private var i:int;
    
       public function HeavyComputer() {}
    
       override public function run() : void
       {
          //heavy computation
          //i++
       }
    
       override public function get percentage() : Number
       {
          return i / 1000000;
       }
    
    }
    Then you create and open the thread and pass your process:
    Code:
    var thread:GreenThread = new GreenThread( new HeavyComputer(), stage.frameRate );
    
    thread.open();
    Before you open it, you can listen for whichever events you need to know about: When the thread completes, when a single process completes, when a process times out, and every thread cycle.

    I'm also going to create a proxy process that will allow you to pass a single method as opposed to creating a class.

    @renderhjs: The image encoding hiccups when part of the bytearray gets compressed. So I could possibly get rid of that if I cared enough to write a compression algorithm in this form. That said, you can do a fairly good job of controlling processing by setting a lower percentage share.

    I'm curious if you were seeing anything like that in the pathfinding demo though- each iteration is 0(n) and performs really well for me.

    Thanks!

  5. #5
    Senior Member
    Join Date
    May 2003
    Location
    Austria
    Posts
    146
    Hi,

    sounds cool. I am interested in your scheduling strategy, if you don´t mind.
    Did you use a common one, or did you implement your own strategy?

    How do you handle critical regions? Do you offer synchronisation in your API?

    Regarding the speed, I have to agree with render. I don´t see much difference between the single- and the multithreaded version.

  6. #6
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    regarding speed, it should be substantially slower than the normal method. Maybe your machine is better enough than mine that you don't see a hiccup? For the pathfinding demo, click opposite corners for the start and end nodes. When I do, and click run, the UI freezes (button hangs in over or selected state) and I might even get the spinning beach ball of death. I don't see any hit at all when running the multithreaded version.

    Not much in the way of scheduling... just adjusting allocation based on how well or poorly each process behaves. basically, i penalize a process if it exceeds its allocation. allocation is, otherwise, evenly broken up amongst all processes. i plan to, in the case of too many processes to maintain the frame rate, simply push the remainder into a queue.

    What exactly do you mean by synchronization?

  7. #7
    Senior Member
    Join Date
    May 2003
    Location
    Austria
    Posts
    146
    regarding speed, it should be substantially slower than the normal method. Maybe your machine is better enough than mine that you don't see a hiccup? For the pathfinding demo, click opposite corners for the start and end nodes. When I do, and click run, the UI freezes (button hangs in over or selected state) and I might even get the spinning beach ball of death. I don't see any hit at all when running the multithreaded version.
    I actually get a hiccup.

    I tested the pathfinding demo with opposite corners and it seemed that the multithreaded version is 20-30 percent slower than the single- one.


    Not much in the way of scheduling... just adjusting allocation based on how well or poorly each process behaves. basically, i penalize a process if it exceeds its allocation. allocation is, otherwise, evenly broken up amongst all processes. i plan to, in the case of too many processes to maintain the frame rate, simply push the remainder into a queue.
    ok, thanks.

    What exactly do you mean by synchronization?
    Usually threads share some data. Synchronization guarantees that you will get always a unique result. Just imagine following scenario:

    ThreadA and ThreadB share the same variable c (=2):

    Thread A: multiplies c by 2;
    Thread B: adds 5 to c;

    So the threads run interleaved (A and B need one cycle to calculate the value):

    cycle thread result
    -----------------------------
    1 A 2
    2 B 4 //result of A
    3 A 9 //result of B
    4 B 18
    5 A 23
    ....

    If B somhow executes the code faster than A (A needs 3 cycles, B 1 cycle), you will get a problem.

    cycle thread result
    -----------------------------
    1 A 2
    2 B 2
    3 A 7//result of B
    4 B 14//result of A
    5 A 19
    ....

    Now you have got two different results. Synchronisation (for example a semaphore) ensures that this won´t happen. You can only access the critical region (in this case c) with one thread, until the critical operation is executed. The other(s) will have to wait.

  8. #8
    Knows where you live
    Join Date
    Oct 2004
    Posts
    944
    There is no synchronization necessary here since its not actually threaded.
    All that is happening is a time consuming algorithm is broken down to allow execution across multiple frames.
    This framework just controls how many steps each algorithm is allowed to run each frame.

    Its an interesting concept, but the problem is that you must manually break the algorithm into finite steps which is often the most difficult part. Adapting a recursive function to be able to stop and restart itself will be far more complicated than choosing how much of it to run each frame.

    You will also run into the issue of how finely to break down the algorithm. Seperating a pathfinding algorithm into performing a single iteration per function call will come at a substantial speed cost. Allowing it to perform 200 iterations per function call may make it too coarse and make it impossible to time properly.

    I'm not sure if I would use the term threading to describe the process of executing an algorithm across several frames.
    The greatest pleasure in life is doing what people say you cannot do.
    - Walter Bagehot
    The height of cleverness is to be able to conceal it.
    - Francois de La Rochefoucauld

  9. #9
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    Quote Originally Posted by andreaskrenmair
    I tested the pathfinding demo with opposite corners and it seemed that the multithreaded version is 20-30 percent slower than the single- one.
    Yeah, it should be a LOT slower- but without the locking.

    Quote Originally Posted by 691175002
    There is no synchronization necessary here since its not actually threaded.
    The idea is that it does emulate threading though; and so to answer andreas, no, i hadn't thought of handling that. It probably wouldn't involve too much to expand it to include semaphores/locking, but at the cost of making it harder to use. In other words, I think that might throw it overboard in terms of approachability.

    Quote Originally Posted by 691175002
    Its an interesting concept, but the problem is that you must manually break the algorithm into finite steps which is often the most difficult part. Adapting a recursive function to be able to stop and restart itself will be far more complicated than choosing how much of it to run each frame.
    I thought the same thing when starting off on this, but it's actually been the case that I haven't even needed to consider writing it to restart. Because the algorithm becomes a datatype, its values are all stored whether it's executing or not. so stopping/restarting is as simple as not executing it. Recursion also ends up being incredibly simple to break apart. It's definitely a different kind of thinking and an interesting algorithmic exercise for sure, but not nearly as difficult as I expected/you assume(?)!

    Quote Originally Posted by 691175002
    I'm not sure if I would use the term threading to describe the process of executing an algorithm across several frames.
    Totally agreed- when I say threading or multi-threading, I mean thread emulation. Everything runs linearly in case I wasn't clear enough about that in my first post. Wikipedia to do a better job than me: http://en.wikipedia.org/wiki/Green_threads It addresses some the problems associated with not being able to execute in a different thread.

    That said, with ShaderJobs we are able to execute (pixel bender) code in a separate thread. I wouldn't be too surprised to see a proper threading api offered in the not-so-distant future.
    Last edited by newblack; 11-16-2008 at 04:53 PM.

  10. #10
    Senior Member
    Join Date
    May 2003
    Location
    Austria
    Posts
    146
    Quote Originally Posted by 691175002
    There is no synchronization necessary here since its not actually threaded.
    All that is happening is a time consuming algorithm is broken down to allow execution across multiple frames.
    This framework just controls how many steps each algorithm is allowed to run each frame.
    Ahh, must have misunterstood something. I should have read the description more carefully. Thanks, for making that clear.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center