隨著多核心架構及平行化運算越來越普及的世代，以開發者的角度而言，如何運用有限的資源，有效地提升產能是很值得深思的一個議題。管線架構在很早之前，就已經被廣泛地運用在各個領域，管線架構的概念可以幫助我們大大地提升產能。我們主要透過將一個核心當作一種服務，組成多條管線來服務各種不同類型的工作流。這種方法可以大量地提升產能，但若是packet的數量不斷的增加，就會造成資源供給的短缺。
在2013 年由O. Rottenstreich 提出pipeline sharing 一種管線共享的概念[16]，可
以解決上述資源不足的問題。但合併之後的管線，會衍生出延遲時間的問題，因此要將哪些管線做合併，可以讓我們在限制的核心數目下，盡可能地找出延遲時間最短的解，正是我們本篇論文所要探討的重點所在。
將不同工作流分配在不同管線上就會產生不同的解，而每個解分別有各自的核心數目及延遲時間，這些解的數量會根據工作流種類呈指數性的成長，會是一個NP-hard 的問題。本論文使用基因演算法的概念來解決此問題，透過基因繁衍的機制找出近似最佳解的答案，並與貪婪演算法之結果和最佳解做比較。

As multi-core architectures and parallel computing become more and more popular, how to effectively increase throughput is a challenge for developer. Pipeline architecture has long been widely used in various fields; the concept of pipeline architecture can help us greatly enhance the system throughput. However, when the number of packets increase, developer has limited number of cores for pipelines. In this thesis we study a novel optimize problem, called pipeline sharing, which is a trade off between the number of needed cores and the average delay.

Our goal is to design the pipeline arrangement of the system to reduce the average delay time under the limited core number. In this thesis, we propose a genetic algorithm for the pipeline sharing problem called PSGA. In PSGA, we design a method to generate our chromosome and use a suitable crossover to solve this problem. Finally, our algorithm can find the solution that approximates optimal solution for large sets of packets. We evaluate our algorithm by one real application called H.264 standard requirements and several synthetic benchmarks.

[1] T. Back, "Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms." Oxford university press, 1996.

[2] J. Clausen, "Branch and bound algorithms-principles and examples." Department of Computer Science, University of Copenhagen, 1999, pp. 1-30.

[3] C. Cui and H. Deng, "Network Functions Virtualisation." SDN and OpenFlow World Congress [White Paper], October. 2012.

[4] T. Dias, N. Roma and L. Sousa, "H.264/AVC framework for multi-core embedded video encoders." International Symposium on SoC, pp. 89-92, 2010.

[5] J. Holland, "Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence." University of Michigan Press, Ann Arbor, 1975.

[6] W. Jiang and V. Prasanna, "Energy-Efficient Multi-Pipeline Architecture for Terabit Packet Classification." IEEE Global Telecommunications Conference, 2009, pp.1-6.

[7] K. Karras, T. Wild and A. Herkersdorf, "A folded pipeline network processor architecture for 100 Gbit/s networks." Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, 2010, pp.2.

[8] I. Keslassy, K. Kogan, G. Scalosub and M. Segal, "Providing performance guarantees in multipass network processors." IEEE/ACM Transactions on Networking, vol. 20, no. 6, pp. 1895-1909, 2012.

[9] A. Land and A. Doig, "An Automatic Method of Solving Discrete Programming Problems." Econometrica: Journal of the Econometric Society, pp. 497-520, 1960.

[10] C. Lee and S. Yang, "Design of an H.264 Decoder with Variable Pipeline and Smart Bus Arbiter." International SoC Design Conference, 2010, pp. 432-435.

[11] S. Martello and P. Toth, "Knapsack problems." Algorithms and computer implementations, 1990.

[12] E. Maslov, M. Batsyn and P. Pardalos, "Speeding up branch and bound algorithms for solving the maximum clique problem." Journal of Global Optimization, vol. 59, no. 1, pp. 1-21, 2014.

[13] H. Nguyen, I. Yoshihara, K. Yamamori, and M. Yasunaga, "Greedy genetic algorithms for symmetric and asymmetric TSPs." IPSJ Transactions on Mathematical Modeling and Its Applications, vol. 43, no. 10, pp. 165-175, 2002.

[14] M. Padberg and G. Rinaldi, "A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems." Society for Industrial and Applied Mathematics Review", vol. 33, no. 1, pp. 60-100, 1991.

[15] T. Pencheva, K. Atanassov, and A. Shannon, "Modelling of a roulette wheel selection operator in genetic algorithms using generalized nets." Int. J. Bioautomation, vol. 13, no. 4, pp. 257-264, 2009.

[16] O. Rottenstreich, I. Keslassy, Y. Revah and A. Kadosh, "Minimizing Delay in Shared Pipelines." IEEE 21st Annual Symposium on High-Performance Interconnects, 2013, pp.9-16.

[17] O. Rottenstreich, I. Keslassy, Y. Revah and A. Kadosh, "Minimizing delay in network function virtualization with shared pipelines." IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 1, pp.156-169, 2017.

[18] H. Sengoku, and I. Yoshihara. "A fast TSP solver using GA on JAVA." Third International Symposium on Artificial Life, and Robotics (AROB III’98), 1998, pp. 283-288.

[19] G. Sullivan, P. Topiwala and A. Luthra, "The H.264/AVC Advanced Video Coding Standard: Overview and Introduction to the Fidelity Range Extensions." Proc. of SPIE Vol, vol. 5558, pp. 455, 2004.

[20] A. Takeda, "Optimization of delivery route in a city area using genetic algorithm." Proc. 4th Int'l Symposium on Artificial Life, and Robotics, 1999, pp. 496-499.

[21] H. Zhan, "A Study on Pipeline Sharing for Multi-core Computing Environments." 2014, Master thesis.