 |
|
|
| Development of a Master-Slave Architecture for Evolutionary Computations |
| Masters |
| Marc Dubreuil |
| Marc Parizeau (Supervisor) |
|
| Problem: Evolutionary algorithms require an enormous computing power to solve problems. Fortunately, problems can easily be divided into several parts and calculated in parallel. It is now possible to purchase low cost computer clusters which are solely used to distribute computations. Moreover, another neglected source of CPU power are networks of PCs that run idle each day for long periods of time. Thus the problem involves designing a parallel and distributed system which can respond to the needs of evolutionary algorithms on a LAN of workstations. This system must perform well, be tolerant to errors, persistent with data, independent of different types of evolutionary algorithms, as well as enable a minimum time lag. This system must also be quantified in order to determine its optimal performance. |
| Motivation: This project is part of the research on evolutionary algorithms carried out in the Computer Vision and Systems Laboratory and is specifically linked to the Open BEAGLE project, an evolutionary algorithm software environment. These algorithms have recently received increasing attention from those who are searching for a means to apply them to complex problems. The solving of these problems often requires days on sequential computers. With the advent of affordable computer clusters, it is possible to solve these complex problems in a parallel and distributed fashion. The ultimate goal of this project is thus to diminish the computing time required to solve complex problems involving evolutionary algorithms. |
Approach: The project is divided into three main steps: the creation of three tools (server, client framework, monitor), the quantification of the system and its validation with concrete examples. The first tool, the server, is optimized to be robust to errors so that if it breaks down, it will resume its work where it left off with a minimum of data loss. Furthermore, a Load Balancing mechanism will be implanted so that each client finishes his computations roughly at the same time, irrespective of their different speeds.
The second tool, the client framework, is responsible of taken charge of communications between the client and the server by making sure that the process is transparent to the user. Since the client can work on a workstations, if a user deactivates the program (e.g. a screen saver), the client should tell the server that it is not computing anymore.
The third tool, the monitor, does not intervene into the evolutionnary computations. It must be able to recognize the state of the problem solving and be able to search for the best data. This tool is therefore indispensable when the problem solving requires days to complete since it will provide a means of monitoring the computation.
All of these tools must be quantified so as to determine the number of clients with whom the server can communicate data before sequential computation becomes more advantageous. Thus, one can determine the number of clients which render the system optimal. The validity of the quantification must then be verified with concrete examples. |
| Challenges: There are already several systems which enable the distribution of evolutionary algorithm data. However, no such system is available or optimized for a LAN of workstations or a cluster of computers and the quantification of such as system has received very little attention. Since our system is optimized for LANs of workstations and is in the area of open source, users will know exactly how many clients should be involved to optimize the problem solving process. |
| Applications: In the near future, this system will be used in two research projects: one in manuscript characters recognition and another one in the design of lens systems. |
| |
| Calendar: September 2002 to December 2004 |
| |
| |
| Last modification: 2007/09/28 by dubreuil |
|
|
