Performance analysis of coarse-grained parallel genetic algorithms on the multi-core sun UltraSPARC T1
Jong-Ho Byun, Kushal Datta, Arun Ravindran, Arindam Mukherjee, Bharat S. Joshi · 2009
The new generation of shared memory multi-core processors with multiple parallel execution paths provides a promising hardware platform for applications with high degree of task-level parallelism (TLP). Genetic Algorithm (GA), a widely-used evolutionary meta-heuristic optimization method, is a unique candidate in this class of applications and demonstrates significant amount of explicit and implicit parallelism. In this paper, we present the performance characteristics of a GA optimizing a placement problem on a Sun UltraSPARC T1 processor. To investigate the behavior of the benchmark, we vary both algorithm-specific parameters as well as the size of the target problem. The system performance is evaluated by monitoring throughput, cycle-per-instruction (CPI) and, the memory access patterns for different core and thread combinations. Our experiments show that for a constant data size, as the number of threads per core increase from 1 to 4, the throughput of the system increases by 84% keeping all cores active. Similarly, as we increase the number of cores in the system, the throughput of the system increases by a factor of 3. The average memory bandwidth is seen to scale in proportion to throughput for both core-scaling and thread-scaling. The overall increase in throughput, either by core-scaling or thread-scaling, in spite of growing memory bandwidth, shows the ability of the multi-threaded multi-core processor to hide long latency memory accesses for the targeted benchmark.