Changes between Version 47 and Version 48 of GAIIA

Timestamp:

Jan 12, 2010, 10:29:56 PM (14 years ago)

Author:

mihai.istin

Comment:

--

GAIIA

@@ -123 +123 @@
 
 
-== The Parallel Solution ==
+== The Algorithm Parallelization ==
+
+'''1. Serial Solution Analysis '''
+
+In order to see what are the most computing expensive parts of the designed algorithm we analyzed first the serial version using Sun Studio Performance Analyzer.
+In the following figure we can see the time taken by different functions called in the algorithm, sorted in descending order. We highlighted (Red) the functions that consume the most cpu time and that can be implemented using openMP. 
+[[Image(grafic2.jpg)]]
+
+
+As can be seen in the above figure, most of the functions of the proposed algorithm have significant execution time (10 to 50%) and can be easily parallelized because they are applied independently to each chromosome from the population. In the next paragraphs we will explain what each function does and how it is better to be parallelized. 
+
+The presented analysis reveals that the most time consuming part of the algorithm is the evaluation (or the computation of fitness for each individual). If we analyze the complexity of this phase of the algorithm we will obtain a O(N*M), where N is the number of nodes, M is the maximum number of predecessor that a node can have. More, this function is applied on each of the C chromosomes leading to a total complexity equals to O(C*N*P). If we also consider that this function is applied on each generation, the total complexity is O(G*C*N*M).
+
+Starting from the complexity of the algorithm the easiest and most efficient way to parallelize this function is to use a parallel for with guided scheduling because some individuals survive to the next generation without been affected by mutation and thus there is no need to be evaluated again. 
+
 
  * The Parallel Execution Model
+
 [[Image(execp.jpg)]]