Difference between revisions of "DocumentationAeminiumRuntime"

Revision as of 22:53, 2 November 2011

The main goal of the Æminium Runtime is to paralyze as much as possible a given code.

Preparing the ground

Downloads

If you are looking for the source code of the Æminium Runtime, all of it may be found here, at a GitHub repository with a read-only version.

Once you have downloaded the files, you may import it into the Eclipse, as a project. In case you are using a different IDE other than this one, you may export its source file and run it under the Apache Ant compiler.

We will soon enough make available all the .jar files so you may include the Æminium Runtime in your own project.

Configuration File

To be updated...

A Simple Program

Creating the tasks

Every Æminium program should begin by creating an instance of the Runtime class using the proper Factory, starting the scheduler by invoking the method init(). It should also be terminated with the shutdown() invocation, but we will remind you about it at the end of the section.

1  public static void main(String[] args)
2  {
3    final Runtime rt = Factory.getRuntime();
4    rt.init();
5  
6    //Your code goes here!
7      
8    rt.shutdown();
9  }

Once you have started the scheduler, it’s time to declare all the tasks and bodies that will turn your program into reality. Every task receives as an argument a body, which it will execute, as well as a short constant from the class Hints, which will provide useful information to the Runtime, so optimization decisions may occur. It should be also noted the existence of the DataGroup, which allows mutual exclusion between two AtomicTasks. It works like a lock, making sure that two AtomicTasks with the same DataGroup won’t be executing simultaneously.

1  /* First, create a body. */
2  Body b1 = new Body() {
3    public void execute(Runtime rt, Task parent) {
4      int sum = 0;
5      for (int i = 0; i < MAX_CALC; i++) {
6        sum += i;
7      }
8
9      System.out.println("Sum: " + sum);
10   }
11 };
12
13 /* Then, create the task. */
14 Task t1 = rt.createNonBlockingTask(b1, Runtime.NO_HINTS);
15 
16 /* Create a data group for an atomic task. */
17 DataGroup dg = rt.createDataGroup();
18 Task t2 = rt.createAtomicTask(b1, dg, Runtime.NO_HINTS);

Although a task and a body are closely related (as you can’t build a task without assigning it a body), you should bear in mind that they don’t necessarily have an exclusive relation. The reason why you keep them separated is because two different tasks may be initialized with the same body. This possibility turns out to be really useful, especially when you want to paralyze a common cycle and divide it through several tasks, for example. With the object that represents the task, you may wish to assign dependencies to it. You only need to give its direct dependencies, although you are free to do as you prefer. Giving a small example, you may have three tasks. The third task depends on the second, while this one depends of the first. This means that the third will depend of the second and the first. At the assignment of the dependencies, you can declare both dependencies, but it is sufficient if you only declare its dependency to the second, assuming that you will say that the second depends on the third. When you start a task, the scheduler takes control of it and it’s to it to decide whether give it work right away or leave it waiting. Therefore, the starting method of a task (Runtime.schedule()) is non-blocking and the rest of the code will be executed immediately.

1  /* There are two ways for building the dependencies.
2   * t1, t2 and t3 are tasks created previously.
3   * Also, deps2 is the collection of dependencies of t2.
4   */ 
5   
6  Collection<Task> deps2 = new ArrayList<Task>();
7  Collection<Task> deps3 = new ArrayList<Task>();
8  
9  /* First option: add all dependencies. */
10 deps2.add(t1); 
11 deps3.add(t1); 
12 deps3.add(t2); 
13  
14 /* Second option: add only direct dependencies. */ 
15 deps2.add(t1);
16 deps3.add(t2);

Life cycle of a task

As has been mentioned in the previous section, a task is allowed to start when you pass it to the scheduler. Then, the scheduler will be responsible for putting the task into work (or better saying, placing it at one of the working queues). One could think that a task would be terminated once it executed all the code present on its body. However, this would mean that the task could be over before all its children were over too, what would bring many problems to the scheduling. Consequently, a task will be considered finished only when it has executed the body and all its children tasks are over too.

1  /* When a thread is create out of the context of another thread,
2   * we mark it has having no parents.
3   * In this example, the second task has a list of dependencies,
4   * while the first has no dependencies.
5   */
6  rt.schedule(t1, Runtime.NO_PARENT, Runtime.NO_DEPS);
7  rt.schedule(t2, Runtime.NO_PARENT, deps2);

As shown in the previous example, the task were launched with the second argument being Runtime.NO_PARENT. This is because these tasks were created out of the context of any other tasks.

An example where this doesn't happen are the following lines, taken from code which doesn't belong to our simple program.

1  private Task createAtomicTask(final Runtime rt, final DataGroup dg1, final DataGroup dg2) {
2    return rt.createAtomicTask(new Body() {
3
4      @Override
5      public void execute(Runtime rt, Task current) {
6        getLogger().info("Atomic Task for data group : " + dg1);
7        try {
8          Thread.sleep(500);
9        } catch (InterruptedException e) {
10         e.printStackTrace();
11       }
12       rt.schedule(createAtomicTask(rt, dg2), current, Runtime.NO_DEPS);
13     }
14   }, dg1, Runtime.NO_HINTS);  
15 }

As you can see on line 12, the task current defines the parent of the task that is created by createAtomicTask(rt, dg2).

Looking inside the machinery

Now that we have looked into the aspect of a simple program, it’s now time to see how everything really works. As the code is executed, every task that is considered ready to be scheduled is placed into the graph, where all its dependencies are present. As this graph is being built by the scheduler, the same entity will have the job of detecting the tasks that have no dependencies and therefore, may start running. When the scheduler finds a task in these conditions, it is placed in one of the available waiting queues. Basically, every processor that can be used by the AEminium program has a corresponding waiting queue, where all the tasks reserved for that processor are pushed into. It’s a job of the scheduler to make a balanced distribution between all the waiting queues, making sure one of the processors isn’t over burden with work while the others are sleeping. Each waiting queue will have a corresponding thread that is looking to the front of the queue and dispatches tasks as they go. If it finds no waiting tasks at its queue, it can pick one of the options. The first, it follows the technique named ‘work stealing’, where it looks in the other queues for tasks that aren’t being processed. If this time saving procedure can’t be taken, the thread falls asleep, till a task is scheduled into its queue.

It should also be noted the existence of a special queue. While these previous queues receive all the non-blocking and atomic tasks, this single queue will accept all the blocking tasks (i.e. the ones which require I/O interaction). This works like a virtual queue, because it has no CPU permanently assigned to it. Instead, it jumps from processor to processor, as they are free from the non-blocking queues' work.

With this, we may define five different states for a task:

• UNSCHEDULED
• WAITING_FOR_DEPENDENCIES
• RUNNING
• WAITING_FOR_CHILDREN
• COMPLETED

Unscheduled is a state that you won’t find very often. A task will be unscheduled if it’s ready to run, but the scheduler hasn’t analyzed it yet. Then, you have the waiting for dependencies state, where a task is blocked due to other task, of which it depends, but haven’t been completed yet. Once all its dependencies are cleaned from the graph (or if the task had no dependencies at the first place) and placed at the waiting queues, a task is marked as running.

If a task terminates before all its children are over too, it passes to the waiting for children state. As soon as all this conditions are fulfilled and this task has nothing else to do, the task is marked down as completed. Note however, that even if a task is completed, it isn’t removed from the graph, having instead only all its dependencies vanished. This happens due to consistency problems, as a task that hasn’t been scheduled yet may depend on this very task and if it was cleaned, it would cause a hole in the dependencies list of the new task. When a task reaches this very completed state, it’s its job to remove all the dependencies that point towards it.

Also, if by any chance this is a child of another task, it’s also its responsibility to take out itself from its parent’s list where references to all the working children are kept. Finally, if the graph happens to be completely empty (meaning there are no dependencies, with the whole set of nodes being marked as completed) and there are no more tasks to schedule, it means the program has terminated and it now time for the scheduler to call the shutdown(). As promised, we remind you the importance of placing the calling of this method at the end of your program, which will be blocked till the graph is cleaned up.

The Code for the Simple Program

1 /**
2  * Copyright (c) 2010-11 The AEminium Project (see AUTHORS file)
3  * 
4  * This file is part of Plaid Programming Language.
5  *
6  * Plaid Programming Language is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10 * 
11 *  Plaid Programming Language is distributed in the hope that it will be useful,
12 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 *  GNU General Public License for more details.
15 *
16 *  You should have received a copy of the GNU General Public License
17 *  along with Plaid Programming Language.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 package aeminium.runtime.examples;
21
22 import java.util.ArrayList;
23 import java.util.Collection;
24 
25 import aeminium.runtime.Body;
26 import aeminium.runtime.Runtime;
27 import aeminium.runtime.Task;
28 import aeminium.runtime.implementations.Factory;
29 
30 public class SimpleTest {
31 	private static int MAX_CALC = 30;
32 
33 	public static void main(String[] args) {
34         final Runtime rt = Factory.getRuntime();
35 		rt.init();
36 
37 		Body b1 = new Body() {
38 			public void execute(Runtime rt, Task parent) {
39 				int sum = 0;
40 				for (int i = 0; i < MAX_CALC; i++) {
41 					sum += i;
42 				}
43 				System.out.println("Sum: " + sum);
44 			}
45 		};
46 
47 		Body b2 = new Body() {
48 			public void execute(Runtime rt, Task parent) {
49 				for (int i = 0; i < MAX_CALC / 5; i++) {
50 					System.out.println("Processing...");
51 				}
52 			}
53 		};
54 
55 		Body b3 = new Body() {
56 			public void execute(Runtime rt, Task parent) {
57 				int max = 0;
58 				for (int i = 0; i < MAX_CALC; i++) {
59 					if (i > max)
60 						max = i;
61 					System.out.println("Calculating Maximum...");
62 
63 				}
64 				System.out.println("Maximum: " + max);
65 			}
66 		};
67 
68 		Body b4 = new Body() {
69 			public void execute(Runtime rt, Task parent) {
70 				Tests.power(2, 20);
71 			}
72 		};
73 
74 		Body b5 = new Body() {
75 			public void execute(Runtime rt, Task parent) {
76 				Tests.matrixMultiplication();
77 			}
78 		};
79 
80 		Task t1 = rt.createNonBlockingTask(b1, Runtime.NO_HINTS);
81 		Task t2 = rt.createNonBlockingTask(b2, Runtime.NO_HINTS);
82 		Task t3 = rt.createNonBlockingTask(b3, Runtime.NO_HINTS);
83 		Task t4 = rt.createNonBlockingTask(b4, Runtime.NO_HINTS);
84 		Task t5 = rt.createNonBlockingTask(b5, Runtime.NO_HINTS);
86 
87 		// ex: deps2 == task2 dependencies
88 		Collection<Task> deps2 = new ArrayList<Task>();
89 		Collection<Task> deps4 = new ArrayList<Task>();
90 		Collection<Task> deps5 = new ArrayList<Task>();
91 
92 		deps2.add(t1);
93 		deps4.add(t1);
94 		deps4.add(t3);
95 		deps5.add(t2);
96 		deps5.add(t4);
97 
98 		rt.schedule(t3, Runtime.NO_PARENT, Runtime.NO_DEPS); // both null and
99 		rt.schedule(t1, Runtime.NO_PARENT, Runtime.NO_DEPS);
100		rt.schedule(t5, Runtime.NO_PARENT, deps5);
101		rt.schedule(t4, Runtime.NO_PARENT, deps4);
102		rt.schedule(t2, Runtime.NO_PARENT, deps2);
103		rt.shutdown();
104	}
105}

Most Important Entities

Runtime

Interface Location: aeminium.runtime.Runtime

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Class Location: aeminium.runtime.implementations.implicitworkstealing

Factory

Class Location: aeminium.runtime.implementations.Factory

Task

Task Interface Location: aeminium.runtime.Task

AtomicTask Interface Location: aeminium.runtime.AtomicTask

BlockingTask Interface Location: aeminium.runtime.BlockingTask

NonBlockingTask Interface Location: aeminium.runtime.NonBlockingTask

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Classes Location: aeminium.runtime.implementations.implicitworkstealing.task

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Notes: Both AtomicTask and BlockingTask extends the main interface Task.

Body

Interface Location: aeminium.runtime.Body

DataGroup

Interface Location: aeminium.runtime.DataGroup

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Classes Location: aeminium.runtime.implementations.implicitworkstealing.datagroup

Hints

Class Location: aeminium.runtime.Hints

Task State

Enumeration Location: aeminium.runtime.implementations.implicitworkstealing.ImplicitTaskState

Graph

Classes Location: aeminium.runtime.implementations.implicitworkstealing.graph

Scheduler

Classes Location: aeminium.runtime.implementations.implicitworkstealing.scheduler

Scheduler

Classes Location: aeminium.runtime.implementations.implicitworkstealing.scheduler

Queues

Class Location: aeminium.runtime.implementations.implicitworkstealing.scheduler.WorkStealingQueue

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Note: As the previous path states, the queues are located inside the Scheduler package.

Error Handler

Interface Location: aeminium.runtime.ErrorHandler

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Classes Location: aeminium.runtime.implementations.implicitworkstealing.error

Events

Classes Location: aeminium.runtime.implementations.implicitworkstealing.events