【冼鏡光並行計算講堂】

【冼鏡光並行計算講堂】

March 20, 2024上線

這是並行處理中文精簡版影片的網頁,在此您可以下載每一講的投影片和程式,也有YouTube上影片的連結。 原來的英文版在此,該網頁提供了37集影片、775張投影片、考試題目的解答和討論。 不過,這是為了Concurrent Computing 這門課錄製的完整課程, 因此預備知識、學生進入這門課之前的先修課目等等和國內的頗不相同,所以這一系列以英文發音的影片對國內同學而言或許會有點障礙。

2020年春天回台時在北科大開了這門課,那時COVID疫情初起,上課都得戴口罩頗不舒服, 好在是和北科大同學交流時了解到國內計算機課程的現狀,心想日後把英文版轉錄成中文版應該是件好事。 但是想到這是一件大工程,不太可能在短期內完成,於是就一而再、再而三地想想(真的只有想)停停,進展全無, 反而時間都用在錄製其他課題上(譬如,初等幾何、程式寫作、空拍機以及FPV等等)。 今(2024年)初終於下定決心開始行動,經過2020年初在北科大的經驗後,我打算只錄製精簡版, 把英文版中一些較艱澀或是較困難的部分去掉(您有了基礎再去看英文版就不會有困難)、 並且加上一些對基本概念的進一步補充,這就是「精簡版」的由來。

教這門課是其來有自的。在1980年代早期,因為電腦預算問題而必須把若干個不完全獨立而是靠中間暫時性檔案連繫的程式整合起來, 研究後發現這些程式可以變成一個大程式中的各個task(IBM的術語)、讓它們並行執行, 原本的暫時性檔案全都去掉而換成在記憶體中使用同步方式的溝通。 這個做法略為增加CPU使用時間和系統服務次數,記憶體用量也有增加但不多,但如此做法卻大大地降低掛磁帶和磁碟的次數、 以及執行程式的次數,算起來可以省不少錢。 不過,IBM卻沒有程式語言提供這種能力,而必須使用組合語言和一些集體指令(macro)完成, 這並不難、多讀手冊找出合用的資訊就行了。 有趣的是,或許是台灣在那個時段沒有人在用並行的能力,雖然所有IBM的OS(含OS和DOS)都有這項能力, 但台灣IBM的技術支援部門卻沒有任何一位工程師懂這套技術。所以,我的並行計算的第一步就是因為工作需要自己踏出第一步、 而且還是獨自跌跌撞撞摸索出來的。

不久之後,在淡江電子計算機系兼任、開了一門OS的課,那時在並行計算方面已經有了初步知識, 因此也希望淡江學生在學校就能學會這一套技巧,以便走入職場後可以立即派上用場。 那個時候,我用兩本書做課本,一本是Madnick和Donovan合寫的 Operating Systems做實務上的介紹(下左照片)、另一本是Per Brinch Hansen的Operating System Principles做並行計算的基礎教材(下右照片),事實上Per Brinch Hansen 的書是第一本有系統地探討並行計算、特別是同步結構的教科書。我想這是十分理想的組合。

沒多久,儒林圖書公司希望我能夠把OS這門課的教材寫成書,我的做法是先把Madnick和Donovan的書譯成中文並且加上很多當時的新內容 (譬如VM — Virtual Machine)、然後補上並行計算的同步概念,但很遺憾的是做完一半後就轉向去做其它的計劃了, 這是我一生中沒有完成心願的遺憾,然而這本書的上冊的確是完成了的(下面照片)。

後來出國進修,拿到PhD學位後沒多久又被指派到教OS(必修)的課程。 到了1990年代,並行計算在電腦界並不陌生,而且幾乎任何好OS課本必然都有這樣的一章到兩章。 然而對很多學生來說,並行是一個很遙遠的觀念, 有一些(他校)教授還告訴我不少學生還會懷疑只有一個CPU的電腦怎麼可能同時執行好幾個程式, 因此我和幾位志同道合的同事決定我們可以做點什麼來克服這一項困難。 在美國國科會(NSF — National Science Foundation)和IBM Eclipse Award支助下, 三年內我們拿到了1200多萬台幣的錢解決這個問題。

我們的做法是設計一組架在C++上方的class library,透過和課本上類似的語法讓學生寫作以C++為主的程式 (那時支援並行處理的C++標準還沒出現),再設計一個visualization系統,它和學生的程式分開執行, 而學生程式中和並行與同步有關的活動則是透過class library和visualization相互溝通(學生不必做任何事)。 這套系統就叫做ThreadMentor。 於是,學生程式中並行活動的細節(特別是同步)在visualization系統幫助之下一覽無遺, 而且各同步項目的彼此互動也可以很清楚地顯示出來。 這套系統最先是在Sun的Solaris 系統下發展,後來再移植到Linux,我們也試著弄出一套Windows XP版, 但是Windows下的東西被Microsoft愈弄愈複雜而且系裡頭也沒多少台Windows的機器, 所以我們最先放棄Windows版,由於Sun和Solaris走入歷史,目前就只有Linux版在運作。 因為計劃已經結束多年,也沒有人力繼續維護,所以目前能夠提供給您的是一個Linux RedHat系統下的全部連結完成的 Intel版static image,大多數Linux系統之下都可以正常工作,Windows或macOS之下就只能開 VM(virtual machine)了,我在北科大開課時就用的是VM。

ThreadMentor完成之後沒幾年, 系中開始修訂課程,決定把OS中的並行部分獨立出來變成一門新課Concurrent Computing, 而原本的OS加上其它內容改成選修,當然Concurrent Computing就是OS的先修課。 於是,Concurrent Computing於焉而生, 每年兩個學期都開課,這已經有10多年的歷史。 當年我們系開出這門課主要是因應愈來愈多的平行和並行計算的需求,在開始時縱使是在美國也是很早、很先進的。 十多年後改成中文的精簡版,希望對國內學子有點幫助。

很多年前,我曾經在國內的論壇提倡過並行處理和同步,但老是遭到冷嘲熱諷, 說是就用package和tool就好、不必學這些「低階」的東西, 或是題目做不出來了就說不是我的學生做不出來理所當然,🙄。 還有很多其它的論調就不多說了,很多年過去了,GPU的並行程式寫作應該很熱門才是,但它的根本就是並行計算。 Concurrent Computing這門課沒講到GPU部分, 因為系裡頭還有一門Multicore程式寫作、內含GPU的部分。 以往,Concurrent Computing最後一兩節課會講GPU程式寫作(使用CUDA), 但後來慢慢地就沒足夠時間講到GPU了。然而,您學會此地的並行概念後跳到GPU部分並不難,因此中文精簡版就沒有這一部分。

以下是各講的影片和投影片,有興趣的朋友不妨有空時來逛逛,看是否有新東西上線。

序號 內容 影片連結 投影片和程式 上線日期
1 開場白。 我們先定義何謂交錯執行、平行和並行;了解一些歷史背景; 再用兩個Unix命令列運算&和|來實現最簡單的並行作業; 接著我們介紹幾個Unix的命令和重導I/O。 影片結束之前有一個Unix的signal的demo,介紹kill命令和 SIGKILLSIGINTSIGSTOPSIGCONT在命令列上的操作。 01-Basics 投影片41頁

程式

March 20, 2024
2 作業系統和硬體基本知識。 本集會討論到以下內容:多處理機系統和它的一些歷史、(dual mode execution)、interrupt和trap(插斷、中斷、和陷阱)、叫用系統(system calls)、計時器(timer)、CPU執行機器指令的週期(instruction execution cycle)包含了讀取指令(fetch) — 解碼(decode) — 執行(execute),CPU pipeline(流程)、資料衝突(data hazards)、不能分割(atomic)指令、特權指令(privileged instruction)等等。從這些討論就不難看出並行計算中某些困難的端倪。 02-Hardware-OS 投影片46頁 May 3, 2024
3 Process 初步:一之二。 本集會討論到以下內容:從原始程式到可執行檔的過程、什麼是一個process、程式的記憶體配置方式(整體資料區、指令區、 heap和stack)、解釋為malloc()calloc()動態記憶體配置用的heap、以及局部變數使用的stack區域。

了解這些最基本的知識之後, 我們討論一個process在執行時的記憶體配置方式、process 在執行時的可能狀態、process的狀態圖。接著是OS處理process的最基本觀念,包含OS內如何表示一個process、process的調度(scheduling)方式、以及切換環境。這些是本課程的必備知識。

本講第二部份是用Unix系統講解多process(multiprocess)程式寫作。我們會討論 fork()exit()wait()函數,並且用例子解說fork()的執行方式和結果;我們也用例子說明fork()產生的process的母-子(parent-child)關係、母和子使用獨立分離的記憶體空間;此外,也提醒在多process程式寫作時printf()所帶來的困擾。最後,我們用若干簡單問題和一道程式習慣做結束。

03-Process-1 投影片70頁

程式

May 19, 2024

最後,有兩組英文發音的教學影片可能會對您有點幫助:

  • 並行計算,英文網頁 在此。這組影片是我教這門課的完全紀錄,已經全部完成。
  • 基本統計觀念和技巧, 網頁在此。這不是正規課程的影片,而是為研究生或有興趣人士錄製的,裡頭包含了從事基本資料分析的知識、觀念和技巧。不過這還是未完成的工作,目前只有三講,都是單變數描述統計學(Descriptive Statistics)的部分,日後會逐漸加強、補充,希望不久之後能做完心目中期望的工作。

更新記事表

  1. 建立日期: March 20, 2024. 第一講上線
  2. 更新 #1:May 3, 2024. 第二講上線
  3. 更新 #2:May 19, 2024. 第三講上線