多核心架構是一種具有高平行度的運算系統。隨著多核心架構的普及，越來越多開發者將嵌入式系統與多核心架構做結合，使其產能大大地超越以往使用單核心架構的嵌入式系統。而管線架構早被應用在各個領域，因其簡單的概念、易於實現的架構以及平行化所帶來的高產能而歷久彌堅。本論文討論在有限的核心數量限制之下，以一顆核心當作一個stage組成多條管線來服務一連串種類不同的工作流時會遇到的管線共用問題。

在管線共用問題上，要讓哪幾種工作流共用同一條管線將會產生出一個解，也就是工作流的分配方案。不同的解會有不同的核心需求以及延遲時間。在這個問題上解的數量將隨著工作流種類指數性地成長。為了在數量龐大的解中得到一個核心需求可接受且延遲時間最短的。本論文分析不同解之間的關係，推導出兩個特性後，提出一Branch and bound演算法，在不比較所有解的前提下提供一個最佳的核心使用方案。在嵌入式系統嚴謹的成本限制之下為開發者提供最短的延遲時間。

本論文中以核心數量的改變來探討所提出演算法得到的最佳解在平均延遲時間上的表現，以及總舉出解的數量和窮舉法的差別。根據實驗結果數據顯示，本論文所提演算法最多只需比較解空間中60%的解，而平均更只需比較近20%的解就可以得出最佳解，證明了本演算法能夠在管線共用這個問題上有效地降低比較次數。

A pipeline is a set of data processing stages, which is popular for improving system performance by paralleling processing units. In this thesis we study a novel optimize problem, called pipeline sharing, which considers the problem of allocating cores between different packet types in order to minimize the average delay. The system we designed is a pipeline-based and multi-core computing model to serve several packet types. Each pipeline in the system processes one or more packet types.

Given the number of cores provided, our goal is to design the pipeline arrangement of the system to reduce the average delay time as possible. We interpret a solution space as a simplified tree structure and suggest two bounding functions by the structure. Finally we propose a branch and bound algorithm based on these bounding functions. Experiment result show that our proposed algorithm finds the optimal solution of the problem by expanding only 20% of all possible solutions in average.

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

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

[3] W. Jiang and V. K. Prasanna, "Energy-Efficient Multi-Pipeline Architecture for Terabit Packet Classification." IEEE Global Telecommunications Conference, (2009).

[4] 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).

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

[6] A. H. Land and A. G. Doig, "An Automatic Method of Solving Discrete Programming Problems." Econometrica, (1960), pp. 497-520.

[7] 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.

[8] S. Martello and P. Toth, "Knapsack problems: algorithms and computer implementations." John Wiley & Sons, Inc, (1990).

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

[10] 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, issue 1, (1991), pp. 60-100.

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

[12] G. J. Sullivan, P. Topiwala and A. Luthra, "The H.264/AVC Advanced Video Coding Standard:Overview and Introduction to the Fidelity Range Extensions." SPIE Conference on Applications of Digital Image Processing XXVII Special Session on Advances in the New Emerging Standard: H.264/AVC, (2004).