Keywords: multicore, task parallel library, C#, parallel.FX, multi-objective evolutionary algorithm, timetabling.

The processing power of desktop machines is increasing over time as a result of the addition of processing cores [1]. This has led to a scenario where developers are adapting to the inherent use of parallelism in their applications, something that was not needed previously.

Threads are one of the most important resources in the development of parallel applications, but their use is complex for those that lack experience in the development of such software. Therefore, especially for Windows systems, there is a need for a simplified toolset that will allow developers to exploit parallelism in the newer generations of processors in an easy and meaningful way.

Parallel.FX is a library that extends the .NET Framework with the implementation of the Task Parallel Library (TPL), which provides a series of parallelization utilities [2], that will become an integral part of the next version of the C# language. The most important improvement implemented in this library, and around which all the functionality that it provides has been built, is the concept of Task. A task may be thought of as an atomic workload which can be launched to execution on any available core within the system, while each core may only receive one single task.

With the purpose of testing this library, we have implemented an academic timetabling problem which is to be solved using a MultiObjective Evolutionary Algorithm, Mixed-Spreading PESA [3]. It is a hybrid algorithm that combines some aspects from PESA [4], NSGA-II [5] and local search. The results obtained demonstrate that the synergy of these methods allows a faster approximation to the Pareto Front. Also, a good generic implementation of this algorithm allows it to be used in a wide variety of problems, including many different test problems, without worrying about code adaptons for each type of problem. In addition, it can be easily redesigned in a parallelized version.

The course timetabling problem can be defined as a a set of encounters organized in time. Each encounter is a combination of resources (rooms, people or equipment), some of which can be specified by the problem while others must be organized as part of the solution. There are many ways to try to solve this NP-Complete problem, such as Tabu-Search or evolutionary algorithms.

Our experiments determined that without a considerable development effort, the run time employed by the software implemented was significantly reduced in comparison with the version which does not use the TPL, indicating that this tool is very useful for the implementation of parallel software.

1

G. Koch, "Discovering MultiCore: Extending the Benefits of Moore's Law", Technology@Intel Magazine, 2005.

2

D. Leijen, J. Hall, "Optimize Managed Code For Multi-Core Machines", MSDN Magazine, 2007.

3

C. Gil, A. Márquez, R. Baños, M.G. Montoya, J. Gómez, "A hybrid method for solving multi-objective global optimization problems", Journal of Global Optimization, 38, 265-281, 2006. doi:10.1007/s10898-006-9105-1

4

D.W. Corne, J.D. Knowles, H.J. Oates, "The Pareto-Envelope based Selection Algorithm for Multiobjective Optimisation", Springer Lecture Notes in Computer Science 1917, 869-878, 2000. doi:10.1007/3-540-45356-3_85

5

K. Deb, S. Agrawal, A. Pratap, T. Meyarivan, "A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multiobjective Optimization: NSGA-II", Springer Lecture Notes in Computer Science 1917, 849-858, 2001. doi:10.1007/3-540-45356-3_83

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £72 +P&P)