Proposal: Task multithreading in NetworkCloudlets
Closed this issue · 4 comments
Detailed information about how the feature should work
Looking at the source code for CloudletExecutionTask.java there is a long comment outlining how task multithreading could work. I want to bring that comment here as a reference and then explain another approach which I think might be better to hopefully get a discussion going for a future PR for this topic. Here is the comment:
* TODO Each execution task must use just a single core.
* It may represent a thread (so the name of the class would be changed).
* By this way, a execution task should use only one core.
* However, tasks may be executed in parallel (considering there are multiple cores)
* and/or sequentially.
* This feature has to be included in the class. One proposal is
* to create a int group attribute. All tasks (not only execution tasks)
* that have the group equals to zero are executed sequentially (that means they
* aren't grouped). The tasks that have the same group have to be executed
* in parallel, one in each CPU core (PE).
* All tasks into a group will be executed together. The next group
* starts only when all the tasks in the prior finishes (each task
* can have a different length, so may finish in different times).
* The value of the group define the tasks execution order.
* Tasks with lower group number are executed first.
* You can have single tasks (that are not grouped) between
* grouped tasks (defining the order that this single task executes)
* just assigning a group number to it and making sure to not
* add other tasks with the same group. For instance, consider the
* tasks below, represented by their group number, for a NetworkCloudlet with 4 cores:
* 0 0 1 1 1 1 2 3 3
*
* there are 2 ungrouped tasks (0) that will be executed sequentially,
* 4 tasks of group 1 that will be executed in parallel after all ungrouped tasks,
* there is a single task at group 2 that will be executed after the group 1
* and finally there is 2 tasks at group 2 to be executed in parallel at the end.
*
* When adding a task to a NetworkCloudlet, the addTask method
* has to check if the current number of tasks for the group (that represents parallel tasks)
* is lower than the number of NetworkCloudlet's PEs.
Visualizing the method described above would create a diagram like this, where every "swimlane" is one PE/Core:
Time ->
----------------------------------------------
0 0 1 2 3
----------------------------------------------
1 3
----------------------------------------------
1
----------------------------------------------
1
----------------------------------------------
This approach does allow for multithreading but in a way that is not super helpful if the tasks in one group depend on each other.
I think that it might be better to use a different approach:
- Again, limit one task to one PE (one Thread).
- Again, create several task groups
- But instead of "vertical grouping" like shown in the diagram above where every task in one group is processed in parallel I suggest "horizontal grouping" where there is one queue for each of the N cores available to the Cloudlet and one queue for waiting task groups.
- The task groups then get assigned to one core and run on it sequentially.
- Taking this a step further, it might be possible to add more "lanes" than there are PEs, performing a time-shared scheduling between them where certain queues "lay dormant" for a while if there aren't enough PEs to go around (which is how real CPUs do it if there are more threads than CPU cores as far as I know).
This makes it easier to model a typical web server where several task groups could be processed in parallel, but the order of tasks in each group must be maintained. The swimlanes would look something like this:
----------------------------------------------
0 0
----------------------------------------------
1 1 1 1
----------------------------------------------
2
----------------------------------------------
3 3
----------------------------------------------
An example scenario where this feature should be used / A brief explanation of why you think this feature is useful
(Combining these two fields)
This feature would be hugely helpful in modeling web servers which should process different requests ( one "request" = one task group with a receive- exec- and send-task ) in parallel. In this scenario the order of tasks in one group is of course critical (can't respond with packets if the calculation is still going on). The first approach would still require the use of group 0 to get ordered execution of the "receive-exec-send"-pipeline which makes it not very helpful because then we are back to using only one core. With the second approach, a new queue with a few tasks can be created for every request. The cloudlet then picks N queues for every simulation step and works on them with one PE per queue (time-sharing).
Representing tasks as r/e/s (receive/execute/send) along with their group id and underscores to indicate length (MIs) the swimlanes look like this:
(5 lanes / 4PEs, one gets chosen to lay dormant during every sim step)
----------------------------------------------
0r 0e_______________0s
----------------------------------------------
1r 1e___________1s 5r 5e______5s
----------------------------------------------
2r 2e___________2s
----------------------------------------------
3r 3e___________________3s
----------------------------------------------
4r 4e_________________________4s
----------------------------------------------
(For example: 3e represents the exec task in group 3 which must run after the receive task 3r but before the send task 3s)
Sorry for the long text and high ambitions, but I really believe that task multithreading as the potential to take simulations of web environments to the next level. I'm excited to work on a PR but I also know that I probably won't be able to get either implementation going without some guidance. Thanks.
Hey @StruffelProductions I really appreciate your contribution.
That is a pretty old TODO which requires a lot of thought.
I suggest you take a look at the contribution guide before start working on some more structural changes.
I don't think it will work that way. I see many issues here.
Firstly, at the current stable stage of the framework, I'm trying to avoid a drastic compatibility break.
If we change NetworkCloudlet to accept a List of CloudletTaskGroup instead of CloudletTask, existing simulations from other researchers won't work anymore. That may be a real pain for them to try to update to a new version, which may be even unfeasible.
Other major issue is that this implementation requires a new kind of CloudletScheduler (CloudletTaskSchedulerSimple) specific for CloudletTasks, which is not realistic. We can have two different kinds of schedulers: time-shared or space-shared. Any of these schedulers may work regardless if we have tasks or not.
Creating a scheduler just because we have new attributes for tasks causes code duplication, increases coupling, bloat the code and makes maintenance harder. That was the approach followed by CloudSim which lead it to software rot and made me create CloudSim Plus.
For instance, they have specific schedulers just for containers, which doesn't make any sense.
Are you really needing such a feature?
I don't see this as a viable way.
Hey @manoelcampos Thanks for the feedback. I can understand all these concerns and I'll try to find a solution that preserves backwards compatibility (in fact, my current planned implementation actually does that, at least in my preliminary tests) and minimizes code duplication as I work in the draft PR.
And even if it is ultimately decided that this is too niche or that the changes would rock the boat too much in the main project I can always release the code as a separate package that can be imported next to CloudSimPlus which extends the existing classes.
I still believe that having multithreading support for modelling web servers that handle requests in parallel would be a big thing, but no hard feelings if all of this ultimately ends up getting rejected.
And even if it is ultimately decided that this is too niche or that the changes would rock the boat too much in the main project I can always release the code as a separate package that can be imported next to CloudSimPlus which extends the existing classes.
Yeah, that is a possible way. On the other hand, that comment on the CloudletExecutionTask could be reconsidered. The proposal was to enable tasks to be either run in parallel or sequentially using some kind of task group.
This proposal possibly is creating complexity. Threads in actual applications are dynamic: they are created at runtime, as implemented by the developer. This way, if we want tasks to be executed in parallel (simulating threads executing in different CPU cores), we could just create the desired number of tasks at a time t.
At runtime, if we want other tasks to be executed just after the previous ones finish, we could only submit those new tasks at that time. This way, we don't need a task group anymore. Cloudlet interface has a listener to notify when the cloudlet finishes executing. We could implement the same feature for tasks.
The researcher may be accountable to submit the tasks at the time he/she wants. If a set of tasks are submitted at time t, they will run in parallell, simulating threads. This way, the execution model does not depend on the CloudletScheduler. Even if a CloudletSchedulerSpaceShared is used, if tasks represent threads, they are executed in parallel (if there are enough CPU cores) or concurrently.
The CloudletSchedulerSpaceShared just ensures that some Cloudlets are queued. But using such a scheduler, if the VM has 4 PEs and there are 4 cloudlets requiring one PE each, two cloudlets are executed in parallel and the other ones wait for the first ones to finish to start executing. The first two Cloudlets that are using the CPU will run their threads (tasks) in parallel.
I still believe that having multithreading support for modelling web servers that handle requests in parallel would be a big thing, but no hard feelings if all of this ultimately ends up getting rejected.
Me too. But such a kind of change must be discussed and designed carefully.
Due to a lack of communication, I'm closing the issue. Feel free to reopen and discuss it first if you intend to provide such a contribution.