多約束贏者全拿類神經網路及其平行分級排程應用

Abstract

贏者全拿(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.