臺灣博碩士論文加值系統

贏者全拿(WTA)及k-贏者全拿(k-WTA)類神經網路被廣泛應用於解決各種基於競爭的問題，由於其高效率的平行計算特性，贏者全拿類神經網路特別適合用於即時應用。然而，現有的贏者全拿模型皆僅將所有的神經元置於單一共同的競爭群體裡面，這嚴重地限制了其應用範圍，於是在此論文中我們提出了一類新的名為k-多限制贏者全拿(k-MCWTA)的類神經網路模型，其考慮神經元分布於多個互相影響的競爭群體中。
我們提出的第一個模型稱為排名Hopfield類神經網路(RHNN)，其為著名的Hopfield類神經網路(HNN)的延伸，專門用來解決1-MCWTA問題。RHNN是由排名神經元所組成，其允許較高排名的神經元可以停用在之前迭代中已啟用的較低排名的神經元；但是將神經元排名無可避免地會導致無法收斂的問題，於是我們提出了兩個定理用以提供RHNN收斂到最佳解的充分條件。然而，另一個問題是RHNN類似於HNN及其他基於能量函數的模型，若以同步的方式更新神經元時，將會產生狀態震盪而無法收斂；於是，在非同步更新神經元的限制下，若RHNN要實現虛擬的平行運算則必須採用連續時間模型，因此必須以類比電路來實現；然而，如今的系統開發平台大多適用於數位設備，故非同步更新神經元的要求變得不切實際。
我們於是提出了另外一個名為離散時間同步排名類神經網路(DSRN)的1-MCWTA模型。DSRN同樣是由排名神經元所組成，但其能夠在完全平行(即，同步)離散時間的方式下運作，因此可以在數位系統中實現。我們透過一個定理證明DSRN會收斂到最佳解，此定理同時提供了收斂延遲的理論上限。最後，為了應付更一般的問題，即k-MCWTA問題，我們引入了一個迭代平行分群演算法(IPGA)，IPGA可以建模為一個離散時間二進制值的雙層遞迴式類神經網路，其中每一個神經元皆可以在完全平行的方式下運作。我們提供了一個定理，用以給出收斂時間的理論上限： ，其中 是神經元的總數；然而在此論文中將會展示在大多數實際情況中，收斂時間會比理論值更為減少許多。
為了展示所提出模型的優越性，我們運用我們上述所提出的類神經網路模型來解決兩個具體的排程問題：用於WDM交換系統的優先性封包排程(1-MCWTA問題)及用於資料中心網路的優先性流量調度(k-MCWTA問題)。模擬結果顯示在一個系統時間槽內的計算時間中，RHNN排程器可以達到接近100%的吞吐量及多層次優先性排程；此外，通過基於CUDA的模擬，DSRN排程器以大約 的收斂延遲實現接近最佳的吞吐量和優先性排程，其中 是交換機埠數；模擬結果還表明IPGA調度器在接近不變的收斂時間下，實現QoS差異化及高達30%的數據中心網路節能效果。

Winner-Take-All (WTA) and k-Winners-Take-All (k-WTA) neural networks have been widely used to solve various competition-based problems. Thanks to highly efficient paral-lel-computation nature, the class of WTA neural networks is especially suitable for real-time practices. However, the existing WTA models simply consider all neurons are within a common competition group, which severely limits the applications of WTAs. In this thesis, we propose a new class of WTA neural networks, called k-multiple-constraints-winners-take-all (k-MCWTA) models, which take consideration of neurons contained in multiple and joint competition groups.
The first model, called Ranked Hopfield Neural Networks (RHNN), is an extension from well-known Hopfield neural network (HNN) and is dedicated for resolving 1-MCWTA problems. Structured with ranked neurons, the RHNN allows higher-rank neurons to disable lower-rank neurons that have been enabled during previous iterations. Ranking the neurons unfortunately gives rise to a convergence problem. We present two theorems that give the sufficient conditions for the RHNN to converge to the optimal solution. This RHNN, howev-er, is similar to HNN and other energy-function-based methods, which give rise to a state os-cillation problem when the neuron updates are in a synchronous manner. Under the con-straint of asynchronous neuron update, for the RHNN to accomplish virtually parallel opera-tion, the neural model must be in continuous-time and hence be implemented in an analogi-cal circuit. However, as the system-design platforms are widely available with digital devic-es, the requirement of asynchronous neuron update becomes impractical.
We thus propose another 1-MCWTA model, called Discrete-time Synchronous Ranked Neural-network (DSRN). DSRN is also structured with ranked neurons, but is capable of op-erating in a fully parallel (i.e., synchronous) discrete-time manner, and thus can be imple-mented in digital systems. We delineate via a theorem that DSRN will converge to the opti-mal solution. The theorem also provides a theoretical upper bound of the convergence la-tency. To cope with more general problem, i.e., k-MCWTA problem, we then introduce an Iterative Parallel Grouping Algorithm (IPGA). IPGA can be modeled as a discrete-time bi-nary-value two-layer recurrent neural network, in which each neuron is capable of operating in a fully parallel manner. We provide a theorem that gives a theoretical upper bound of the convergence time, , where is the total number of neurons. As will be shown in the thesis, the convergence time can be largely reduced in most real cases.
To demonstrate the superiority of proposed models, we apply our methods to resolve two specific scheduling problems: prioritized packet scheduling (1-MCWTA problem) for WDM switching system and prioritized flow scheduling (k-MCWTA problem) for data cen-ter networks. Simulation results show that, with the computation time within one system slot time, the RHNN scheduler achieves near 100% throughput and multi-level prioritized sched-uling. Moreover, via CUDA-based simulations, the DSRN scheduler achieves near-optimal throughput and prioritized scheduling, with nearly convergence latency, where is the switch port count. The simulation results also show that the IPGA scheduler achieve QoS differentiation and up to 30% energy saving for data center network, with near-ly constant convergence time.

摘 要 i
ABSTRACT iii
誌 謝 v
目 錄 vi
表 目 錄 viii
圖 目 錄 ix
符 號 說 明 xi
I. Introduction 1
II. Winner-Take-All Problems 4
III. Winner-Take-All Neural Networks 8
A. Hopfield Neural Network (HNN) 8
B. Ranked Hopfield Neural Network (RHNN) 10
C. Discrete-time Synchronous Ranked Neural-network (DSRN) 17
D. Iterative Parallel Grouping Algorithm (IPGA) 22
IV. Application 1: Prioritized Packet Scheduling for WDM Switching System 33
A. Background 33
B. Problem Definition 34
C. RHNN Prioritized Packet Scheduler 40
D. DSRN Prioritized Packet Scheduler 48
V. Application 2: Prioritized Flow Scheduling for Data Center Networks 55
A. Background 55
B. Problem Definition 56
C. IPGA Prioritized Flow Scheduler 60
VI. Conclusions 67
參 考 文 獻 68

[1] Z. Yi, P. Heng, and P. Fung, “Winner-Take-All Discrete Recurrent Neural Networks,” in IEEE Transactions on Circuits and Systems – II: Analog and Digital Signal Processing, vol. 47, no. 12, Dec. 2000, pp. 1584-1589
[2] E. Majani, R. Erlanson, and Y. Abu-Mostafa, “On the k-winners-take-all network,” in Advances in Neural Information Processing Systems, vol. 1, D. S. Touretzky, Ed. San Mateo, CA: Morgan Kaufmann, 1989, pp. 634-642.
[3] R. Erlanson and Y. Abu-Mostafa, “Analog neural networks as decoders,” in Advances in Neural Information Processing Systems, vol. 1, R. P. Lippmann, J. E. Moody, and D. S. Touretzky, Eds. San Mateo, CA: Morgan Kaufmann, 1991, pp. 585-588.
[4] T. M. Kwon and M. Zervakls, “KWTA networks and their applications,” Multidimen-sional System Signal Processing, vol. 6, no 4, pp. 333-346, 1995.
[5] A. Yuille and D. Geiger, “Winner-take-all networks,” in The Handbook of Brain Theory and Neural Networks, 2nd ed. Cambridge, MA: MIT Press, 2003, pp. 1228-1231.
[6] X. Hu and J. Wang, “An Improved Dual Neural Network for Solving a Class of Quad-ratic Programming Problems and Its k-Winners-Take-All Application,” IEEE Transac-tion on Neural Networks, vol. 19, no.12, Dec. 2008, pp. 2022-2031.
[7] J. Wang, “Analysis and Design of a k-Winners-Take-All Model with a Single State Var-iable and Heaviside Step Activation Function,” IEEE Transactions on Neural Networks, vol. 21, no. 9, Sep. 2010, pp. 1496-1506.
[8] C. Lin and C. S. Lee, “Neural Fuzzy Systems: A Neuro-Fuzzy Synergism to Intelligent Systems,” Prentice Hall, 1996.
[9] X. Hu and B. Zhang, “A New Recurrent Neural Network for Solving Convex Quadratic Programming Problems with an Application to the K-winners-take-all Problem,” IEEE Trans. Neural Networks, vol. 20, no. 4, April 2009, pp. 654-664.
[10] Q. Lin, C. Dang, and J. Cao, “A Novel Recurrent Neural Network with One Neuron and Finite-time Convergence for K-winners-take-all Operation,” IEEE Transactions on Neural Networks, vol. 21, no. 7, Jul. 2010.
[11] P. Tien and B. Ke, “Parallel QoS Scheduling for WDM Optical Interconnection System using a New Ranked Hopfield Neural Network,” IEEE/OSA JLT, vol. 29, no. 16, pp. 2436-2446, Aug. 2011.
[12] P. Tien and B. Ke, “Parallel Prioritized Scheduling for WDM Optical Switching System,” IEEE HPSR, pp. 86-91, 2013.
[13] B. Ke, P. Tien, and Y. Hsiao, “Parallel Prioritized Flow Scheduling for Software Defined Data Center Network,” IEEE HPSR, pp. 217-218, 2013.
[14] A. Kodi and A. Louri, “Multidimensional and Reconfigurable Optical Interconnects for High-Performance Computing (HPC) Systems,” J. Lightw. Technol., vol. 27, no. 21, Nov. 2009, pp. 4634-4641.
[15] S. Scott, “Optical Interconnects in Future HPC System,” IEEE/OSA Optical Fiber Communication Conference, 2011.
[16] A. Wonfor, H. Wang, R. V. Penty, and I. H. White, “Large Port Count High-speed Opti-cal Switch Fabric for Use within Datacenters,” IEEE/OSA Journal of Optical Commu-nications and Networking, vol. 3, no. 8, Aug. 2011, pp. A32-A39.
[17] T. Wang et al., “All-optical Switching Data Center Network Supporting 100Gbps Up-grade and Mixed-line-rate Interoperability,” IEEE/OSA Optical Fiber Communication Conference, 2011.
[18] M. Yuang, Y. Lin, J. Shih, J. J. Chen, P. Tien, S. S. W. Lee, and S. Lin, ‘A QoS Optical Packet Switching System: Architectural Design and Experimental Demonstration,” IEEE Comm. Mag., May 2010, pp. 66-75.
[19] G. Papadimitriou, C. Papazoglou, and A. Pomportsis, “Optical Switching: Switch Fab-rics, Techniques, and Architectures,” J. Lightw. Technol., vol. 21, no. 2, Feb. 2003, pp. 384-405.
[20] K. A. Williams, G. F. Roberts, T. Lin, R. V. Penty, I. H. White, M. Glick, and D. McAuley, “Integrated Optical 2x2 Switch for Wavelength Multiplexed Interconnects,” IEEE J. Sel. Topics Quantum Electron., vol. 11, no. 1, Jan./Feb. 2005, pp. 78-85.
[21] S. Liew, G. Hu, and H. Chao, “Scheduling Algorithms for Shared Fiber-Delay-Line Op-tical Packet Switches - Part II: The Three-Stage Clos-Network Case,” J. Lightw. Tech-nol., vol. 23, no. 4, Apr. 2005, pp. 1601-1609.
[22] B. Sarker, T. Yoshino, and S. Majumder, “All-Optical Wavelength Conversion Based on Cross-Phase Modulation (XPM) in a Single-Mode Fiber and a Mach-Zehnder Interfer-ometer,” IEEE Photon. Technol. Lett., vol. 14, no. 3, March 2002, pp. 340-342.
[23] T. Tanemura, M. Takenaka, A. Amin, K. Rakeda, T. Shioda, M. Sugiyama, and Y. Nakano, “InP-InGaAsP Integrated 1x5 Optical Switch Using Arrayed Phase Shifters,” IEEE Photon Technol. Lett., vol. 20, no. 12, June 2008, pp. 1063-1065.
[24] I. M. Soganci et al., “Monolithically Integrated InP 1x16 Optical Switch with Wave-length-Insensitive Operation,” IEEE Photon. Technol. Lett., vol.no. 3, Feb. 2010, pp. 143-145.
[25] A. Jajszczyk, “Nonblocking, Repackable, and Rearrangable Clos Networks: Fifty Years of the Theory Evolution,” IEEE Comm. Magazine, vol. 41, no. 10, Oct. 2003, pp. 28-33.
[26] T. P. Troudet and S. M. Walters, “Neural Network Architecture for Crossbar Switch Control,” IEEE Trans. On Circuits and Systems, vol. 38, no. 1, Jan. 1991, pp. 42-56.
[27] K. Symington, A. Waddie, M. Taghizadeh, and J. Snowdon, “A Neural-Network Packet Switch Controller: Scalability, Performance, and Network Optimization,” IEEE Trans. On Neural Networks, vol. 14, no. 1, Jan. 2003, pp. 28-34.
[28] E. Oki, R, Pojas-Cessa and H, Chao, “A pipeline-based approach for maximal-sized matching scheduling in input-buffered switches,” IEEE Communication Letters, vol. 5, Jun. 2001, pp. 263-265.
[29] C. Minkenberg, L. Iliadis and F. Abel, “Low-latency pipelined crossbar arbitration,” IEEE GLOBECOM 2004, vol. 2, 2004, pp. 1174-1179.
[30] L. Liu, Z. Zhang and Y. Yang, “Pipelining Packet Scheduling in a Low Latency Optical Packet Switch,” IEEE INFOCOM 2011, pp. 3083-3091.
[31] Z. Zhang and Y. Yang, “WDM Optical Interconnects with Recirculating Buffering and Limited Range Wavelength Conversion,” IEEE Trans. Parallel and Dist. Syst., vol. 17, no. 5, May 2006, pp. 466-480.
[32] J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,” Proceedings of OSDI, 2004.
[33] Apache Hadoop Project. http://hadoop.apache.org/.
[34] M. Al-Fares, A. Loukissas, and A. Vahdat, “A Scalable, Commodity Data Center Net-work Architecture,” in Proceedings of ACM SIGCOMM, 2008.
[35] A. Greenberg, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. Maltz, P. Patel, and S. Sengupta, “VL2: A Scalable and Flexible Data Center Network,” in Proceedings of ACM SIGCOMM, 2009.
[36] C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, “BCude: A High Performance, Server-Centric Network Architecture for Modular Data Centers,” in Proceedings of ACM SIGCOMM, 2008.
[37] C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang, and S. Lu, “DCell: A Scalable and Fault-tolerant Network Structure for Data Centers,” in Proceedings of ACM SIGCOMM, 2008.
[38] Open Networking Foundation, “Software-defined networking: the new norm for net-works,” ONF White Paper, April 13, 2012.
[39] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling Innovation in Campus Networks,” ACM SIGCOMM CCR, 2008.
[40] OpenFlow. http://www.openflow.org/.
[41] Cisco Data Center Infrastructure 2.5 Design Guide. http://www.cisco.com/univercd/cc/td/doc/solution/dcidg21.pdf.
[42] C. Hopps, “Analysis of an Equal-Cost Multi-Path Algorithm,” IETF, 2000, RFC 2992.
[43] M. Al-Fares, S. Radhakrishnan, B. Raghva, N. Huang, and A. Vahdat, “Hedera: dynamic flow scheduling for data center networks,” Proceedings of NSDI Symposium, 2010.
[44] B. Heller, S. Seetharaman, P. Mahadevan, Y. Yiakoumis, P. Sharma, S. Banerjee, and N. McKeown, “ElasticTree: Saving Energy in Data Center Networks,” Proceedings of NSDI Symposium, 2010.
[45] P. Graubner, M. Schmidt, and B. Freisleben, “Energy-Efficient Virtual Machine Con-solidation,” IT Professional, vol. 15, issue 2, March-April 2013, pp. 28-34.
[46] H. Goudarzi and M. Pedram, “Energy-efficient VM replication and placement in a cloud computing system,” IEEE Int. Conf. on Cloud Computing, pp. 750-757, 2012.