旋律辨識在叢集PC下之研究與實作

Research and Implementation of Melody Recognition on Clustered PCs

邱紹雄(Shao-Hsiung Leo Chiu)

指導教授 ： 張智星

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2008年)

https://doi.org/10.6843/NTHU.2008.00230

摘要

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

關鍵字

平行處理 ； 旋律辨識 ； 叢集 ； CBMR

並列摘要

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.

參考文獻

[15] Jiang-Chun Chen and J.S. Roger Jang “Parallel Processing of Content-based Music Retrieval”, MS Thesis, National Tsing Hua University, Taiwan, 2001.

[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