The Hardware Design for a Genetic Algorithm Accelerator for Packet Scheduling Problems

Yang-Han Lee; Yih-Guang Jan; Yun-Hsih Chou; Hsien-Wei Tseng; Ming-Hsueh  Chuang; Shiann-Tsong Sheu; Yue-Ru  Chuang; Jei-Jung Shen; Chun-Chieh Fan

doi:10.6180/jase.2008.11.2.08

The Hardware Design for a Genetic Algorithm Accelerator for Packet Scheduling Problems

Yang-Han Lee This email address is being protected from spambots. You need JavaScript enabled to view it.¹, Yih-Guang Jan¹ , Yun-Hsih Chou² , Hsien-Wei Tseng¹ , Ming-Hsueh Chuang¹ , Shiann-Tsong Sheu³ , Yue-Ru Chuang¹ , Jei-Jung Shen¹ and Chun-Chieh Fan⁴

¹Department of Electrical Engineering, Tamkang University, Tamsui, Taiwan 251,R.O.C.
²Department of Electronic Engineering, St. John’s University, Tamsui, Taiwan 251, R.O.C.
³Department of Communication Engineering, National Central University, Taoyuan, Taiwan 320, R.O.C.
⁴Department of Computer & Communication Engineering, St. John’s University, Tamsui, Taiwan 251, R.O.C.

Received: May 5, 2005
Accepted: June 18, 2007
Publication Date: June 1, 2008

Download Citation: ||https://doi.org/10.6180/jase.2008.11.2.08

ABSTRACT

In the basic genetic algorithm and its variations, they usually process the calculations in a sequential way so that the waiting time for every generation member awaited to be processed increases dramatically when the generation evolution continues. Consequently the algorithm converging rate becomes a serious problem when we try to apply the genetic algorithm in real time system operations such as in the packet scheduling and channels assignment in the fiber optic networks. We first propose in this paper a genetic algorithm accelerator which has the capability not only to accelerate the algorithm convergent rate but also to have its solution to reach the problem’s optimum solution. Then we develop hardware blocks such as the blocks of Base Generator, Operation Selector, Delta Calculator, Duplicate Priority Encoder, Abort Priority Encoder and Next Generator, etc. to realize this proposed generic algorithm accelerator. Due to these hardware blocks realizations it will enhance the speed of the algorithm converging rate and make certain its convergent solution reaches the problem’s optimum solution.

Keywords: Genetic Algorithm, Packet Scheduling, Base Generator, Operation Selector, Delta Calculator, Duplicate Priority Encoder, Abort Priority Encoder, Next Generator

REFERENCES

[1] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, MA (1989).
[2] Lee, J. H. and Un, C. K., “Dynamic Scheduling Protocol for Variable-Sized Messages in A WDM-based Local Network,” J. Lightwave Technol., pp. 15951600 (1996).
[3] Babak Hamidzadeh, Ma Maode and Mounir Hamdi, “E_cient Sequencing Techniques for Variable-Length Messages in WDM Network,” J. Lightwave Tech., Vol. 17, pp. 13091319 (1999).
[4] Sengupta, S. and Ramamurthy, R, “From Network Design to Dynamic Provisioning and Restoration in Optical Cross-connect Mesh Networks: An Architectural and Algorithmic Overview,” IEEE Network, Vol. 15, pp. 4654 (2001).
[5] Paul Green, “Progress in Optical Networking,” IEEE Communications Magazine, Vol. 39, pp. 5461 (2001).
[6] Hou, Edwin S. H., Nirwan Ansari and Hong Ren, “A Genetic Algorithm for Multiprocessor Scheduling,” IEEE Transaction on Parallel and Distributed Systems, Vol. 5 (1994).
[7] Sheu, S.-T., Chuang, Y.-R., Cheng, Y.-J. and Tseng, H.-W., “A Novel Optical IP Router Architecture for WDM Networks,” Proceedings of IEEE ICOIN-15, pp. 335340 (2001).
[8] Sheu, S.-T. and Chuang, U.-J., “An Optimization Solution for Packet Scheduling: A Pipeline-Based Genetic Algorithm Accelerator,” Proc. Of AAAI GECCO’ 2003, Chicago (2003).