在旋律辨識的領域中，CBMR (Content-based Music Retrieval)系統藉由使用者輸入的歌聲或樂曲，在基頻萃取後經由比對資料庫中的MIDI檔而找出最接近的歌曲。不過由於歌曲的比對過程繁瑣且複雜，需要龐大的計算能力，而在單一伺服器的情況之下，其計算能力是有所侷限的。為了解決這個問題，因而有了平行運算的系統模式出現，也同時間大幅增進了計算效率。
若考慮到同一時間內有大量使用者使用平行系統的情況下，整體使用者所花費的時間勢必隨著使用者數量增加而上升。本論文就是以此為出發點的立意下展開探討，包括使用Round Robin排程分散使用者需求於各伺服器、系統在單一需求與同時多需求間轉換的情況考量、以及針對單一歌曲計算時間縮短的方法探討。一般而言，原本佇列式排程的平行運算系統(五台次伺服器)在同時間100個需求進入的狀況下使用線性伸縮方法從頭比對每個需求的平均反應時間約為24秒，而在使用Round Robin排程的新系統架構下，平均反應時間已可降低為10秒左右。
本篇論文還討論了一種基於平行運算系統架構的辨識加速方法。利用主、次伺服器間的資訊交換，即時更新輸入歌曲與比對歌曲間比對距離的最低門檻值，一旦計算結果超出最低門檻值便停止並進行下一次計算，藉此縮減辨識時多餘的時間浪費，進而達到加速的效果。

In the task of melody recognition, CBMR (Contend-based Music Retrieval) system searches for a query song by extracting features from the acoustic input from the user and comparing them with the songs in the MIDI database. Due to the computational complexity of similarity comparison of song features, the performance is limited under the single server settings. In order to alleviate this problem, parallel computing was invented to increase the computation efficiency.
If a large number of users are accessing the parallel computing system simultaneously, the overall response time would increase with the increasing number of users. This thesis discusses several solutions to the above problem, including a Round Robin strategy to distribute the user requests to several slave servers, mode switching consideration between single request and simultaneous multi-request, and comparison computation reduction techniques. In general, by using the parallel system with the queue strategy (5 slave servers) and adopting linear scaling and searching-from-beginning techniques, the average response time for 100 simultaneous requests is 24 seconds. Under the new framework of Round Robin system, the average response time can be reduced to around 10 seconds.
On the other hand, this thesis also discusses an approach to accelerate the recognition process based on clustered PCs. It updates the threshold distance between the query song and the compared song in real time by exchanging information between master and slave servers. The current calculation is aborted once the partial computation result is larger than the threshold distance and the comparison for the next song is started immediately. Thus, the time is saved for unnecessary computation and the efficiency is increased.

摘 要 1
Abstract 2
致 謝 3
目 錄 4
圖 表 目 錄 6
第一章 導論 7
1.1 研究主題 7
1.2 相關研究簡介與比較 8
1.3 章節概要 9
第二章 平行處理的分散式檢索系統 10
2.1 系統概述 10
2.2 負載分配 11
2.3 搜尋方法 11
2.3.1 Dynamic Time Warping (DTW) 11
2.3.2 線性伸縮 (Linear Scaling) 13
2.3.3 2-level search 14
2.4 主、次伺服器考量 14
2.4.1 主伺服器考量 14
2.4.2 次伺服器考量 14
2.5 多核心處理器 15
2.6 失誤偵測與自動回復 15
2.7 異質性平台下的問題 16
2.8 加速技巧 17
2.9 多需求量下所產生的問題 18
第三章 多需求量的平行處理系統 19
3.1 系統架構 19
3.2 次伺服器的運算數量分配 20
3.3 單一與大量需求切換的考量 20
第四章 實驗結果與探討 21
4.1 實驗環境 21
4.2 實驗結果與分析 22
4.2.1 次伺服器反應時間收斂情況 22
4.2.2 多核心處理器模擬多伺服器的運算效能 24
4.2.3 主、次伺服器溝通的加速方法效能 27
4.2.4 多需求平行處理系統的運算效能 29
4.2.5 單一需求與多需求平行處理系統切換 31
4.3 結論 32
第五章 未來工作 33
5.1 其它適合平行處理的比對方法 33
5.2 自動搜尋網際網路上的音樂資訊 33
5.3 利用雲端運算技術提昇平行處理效能 34
第六章 結論 35
參考文獻 36

[1] JT Foote, “Content-based retrieval of music and audio”, Proceedings of SPIE,
PP. 138-147, 1997
[2] Kai Hwang, Faye A. Briggs, “Computer Architecture and Parallel Processing”, McGraw-Hill, Inc, 1990
[3] Dave Thomas, “Enabling Application Agility - Software as A Service, Cloud Computing and Dynamic Languages”, Journal of Object Technology, vol. 7 no. 4, PP. 29-32, June 2008
[4] Asif Ghias, Jonathan Logan, David Chamberlain, Brain C. Smith,” Query by humming: musical information retrieval in an audio database”, Proceedings of the third ACM international conference on Multimedia, PP. 231-236, 1995.
[5] Whitney K. Newey and Kenneth D. West, “A Simple, Positive Semi-Definite, Heteroskedasticity and Autocorrelation Consistent Covariance Matrix”. Econometrica, Vol. 55, No. 3, PP. 703-708, May 1987.
[6] Roger J. McNab, Lloyd A. Smith, David Bainbridge and Ian H. Witten, “The New Zealand Digital Library MELody inDEX”, D-Lib Magazine, May 1997.
[7] Chen, A.L.P., M. Chang, J. Chen, J.L. Hsu, C.H. Hsu, and Hua, S.Y.S., “Query by Music Segments: An Efficient Approach for Song Retrieval”, Proc. of IEEE International Conference on Multimedia and Expo, 2000.
[8] Sih G.C. and Lee E.A., “Dynamic-level scheduling for heterogeneous processor networks”, Parallel and Distributed Processing, 1990

[9] Henan Zhao and Rizos Sakellariou, “An Experimental Investigation into the Rank Function of the Heterogeneous Earliest Finish Time Scheduling Algorithm”, Springer Berlin / Heidelberg, 2004
[10] MA Iverson, F Ozguner, and GJ Follen, “Parallelizing existing applications in a distributed heterogeneous environment”, 4th Heterogeneous Computing Workshop, 1995
[11] Y.P. Chen and Y.C. Chung, “A Performance-Efficient Task Duplication-Based Scheduling Algorithm for Heterogeneous Computing”, MS Thesis, National Tsing Hua University, Taiwan, 2005
[12] Benjamin Chen and J.S. Roger Jang, “Query by singing”, MS Thesis, National Tsing Hua University, Taiwan, 1998.
[13] I-Yang Lee, J.S. Roger Jang, and Wen-Hao Hsu “Content-based Music Retrieval from Acoustic Input”, 12th IPPR Conference on Computer Vision, Graphics, and Image Processing, PP. 325-330, Taiwan, Aug 1999.
[14] Ming-Yang Gao and J.S. Roger Jang “A Query-by-Singing System based on Dynamic Programming”, International Workshop on Intelligent Systems Resolutions (the 8th Bellman Continuum), PP. 85-89, Hsinchu, Taiwan, Dec 2000.
[15] Jiang-Chun Chen and J.S. Roger Jang “Parallel Processing of Content-based Music Retrieval”, MS Thesis, National Tsing Hua University, Taiwan, 2001.
[16] W. Richard Stevens “Unix network programming”, Volume 1, 2nd, Prentice Hall, 1998.
[17] Silberschatz Calvin “Operating system concepts”, Fifth edition, Addison Wesley, 1998.
[18] Mache Creeger “Multicore CPUs for the Masses”, QUEUE, page 64-65, 2005.
[19] M. Shreedhar and George Varghese “Efficient fair queueing using deficit round-robin”, IEEE/ACM Transactions on Networking, Volume 4, Issue 3, PP. 375 – 385, 1996.
[20] Sridharan, Prashant, “Advanced Java Networking”, Prentice Hall, 1997.
[21] 張智星，“Matlab程式設計 入門篇”，鈦思科技，2007。