基于GPU的混合蛙跳算法改進

牛寶童 錢宇浛

摘? 要： 【目的】 將混合蛙跳算法的求解過程轉(zhuǎn)化為CUDA線程，提出并研究基于GPU的并行混合蛙跳算法，加快算法尋優(yōu)過程，提高混合蛙跳算法的運算速度，以此促進群體智能優(yōu)化算法的并行研究及應(yīng)用。【方法】 本文采用了CPU+GPU異構(gòu)形式進行計算，其中GPU負責對大規(guī)模的密集型數(shù)據(jù)進行設(shè)計分析以及計算，而對于CPU來講，負責開展事務(wù)管理以及復(fù)雜邏輯運算等不適合數(shù)據(jù)并行的計算模塊。【結(jié)果】 將混合蛙跳算法的求解過程轉(zhuǎn)化為CUDA線程，實現(xiàn)基于GPU的并行混合蛙跳算法。在GPU上加速執(zhí)行以提高算法運行速度，在保證與串行混合蛙跳算法相同優(yōu)化性能的同時提高加速比。【結(jié)論】 （1）對于ISFLA算法它采用了并行調(diào)度的形式展開計算分析，對于虛擬機之間的負載起到了很好的平衡作用，減小了負載間的平衡度對于整體的工作時間來講起到了很好的縮短作用。（2）ISFLA算法產(chǎn)生的初始種群有著更好的質(zhì)量，這能夠?qū)⒁恍┍憩F(xiàn)不好的個體進行排除，加快了整體的收斂速度，減小了進行搜索迭代的時長。

關(guān)鍵詞： 混合蛙跳算法;圖形處理器;統(tǒng)一計算設(shè)備架構(gòu);群體智能優(yōu)化算法

中圖分類號： TP391.41 ???文獻標識碼： A??? DOI：10.3969/j.issn.1003-6970.2020.07.031

本文著錄格式：牛寶童，錢宇浛. 基于GPU的混合蛙跳算法改進[J]. 軟件，2020，41（07）：152-158

Improved GPU-based Hybrid Frog Leaping Algorithm

NIU Bao-tong¹， QIAN Yu-han²

（1. College of Information Science and Technology， Gansu Agricultural University， Lanzhou 730070， Gansu， China;2. China Aerospace Science and Technology Corporation，Ninth Research Institute， Beijing 100094， China）

【Abstract】： [Objective] Transform the solution process of the hybrid frog leap algorithm into a CUDA thread， propose and study a parallel hybrid frog leap algorithm based on GPU， speed up the algorithm optimization process， increase the operation speed of the hybrid frog leap algorithm， and promote parallel research and application of swarm intelligent optimization. [Method] It adopts the CPU + GPU heterogeneous model. The CPU is responsible for performing complex logic processing and transaction management that are not suitable for data parallel computing. The GPU is mainly responsible for computing-intensive large-scale data parallel computing. [Results] The solution process of the hybrid frog leap algorithm is transformed into a CUDA thread， and a parallel hybrid frog leap algorithm based on GPU is realized. Accelerate the execution on the GPU to increase the speed of the algorithm， and improve the speedup while ensuring the same optimized performance as the serial hybrid frog leap algorithm. [Conclusion] （1） The ISFLA algorithm uses a parallel scheduling model to execute tasks， which effectively balances the load between virtual machines， reduces the load balance degree， and shortens the overall completion time of the workflow. （2） The quality of the initial population generated by ISFLA is better， which can effectively exclude some poorly performing individuals， thereby shortening the search iteration time and accelerating the convergence speed.

【Key words】： Hybrid frog jumping algorithm; graphics processor; unified computing device architecture; swarm intelligence optimization algorithm

0? 引言

目前伴隨著科學技術(shù)的快速發(fā)展，在進行科研以及日常活動中經(jīng)常會碰到一些需要進行最優(yōu)化求解的問題，對于最優(yōu)化求解的問題如何獲得一種既簡單有高效的方式目前成為眾多學者要開展研究的主要方向之一。……