Multi-SPARC Virtual Platform -- 品皓

======================5/17============================
meeting投影片

利用之前完成的觀測instruction cycle執行數的功能，觀測自己寫的矩陣相乘程式。

40X40 矩陣相乘，分給四個core，切割方式是每一個task計算出一個element，也就是說每個task接收80個elements，處理40個乘加運算，最後產生一個element並送出。總共有1600個task。一個task所需的instruction cycle數:
wait input: 557
calculation: 2119
send output: 82

以上是平均的結果，但是meeting時大家疑問為什麼40個乘加需要花費這麼多instruction?

之後檢討，觀察assembly code，一個整數的乘法是呼叫一個function .umul


.umul 是在做bit的乘法(mulscc)，也就是說一個32 bit的整數他需要做32次mulscc


其中的原因是sparc gcc預設是產生v7的instuction code，為了產生v8的必須加上參數-mcpu=v8。產生的結果是一個整數乘法只需一個instuction完成(smul)。



v8 task所需的instruction cycle數:
wait input: 481
calculation: 354
send output: 82

整個40x40的矩陣相乘所需的instruction cycle數
wait input: 191919 ~ 192591
calculation: 141645
send output: 32718

wait input數據有點差距的原因是程式的行為，開始是四個core同時在等待input，但是外部module送input data卻是一次只能送一個，所以才會造成這一點差距。

======================4/26============================
主要是完成上禮拜做一半的事情，完成外部module透過Multi-core’s Interface與core溝通的能力；並改寫應用程式: 矩陣相乘，改成input & output data皆由ELF sender收送。

另外一個是觀測instruction執行數的功能。
寫成一個應用程式(ELF)可呼叫的function，包在library裡。功用是回傳目前執行總cycle數。
用法跟一般timer類似，想紀錄一段測試程式執行所花費的cycle數時，在測試程式執行前紀錄當下時間，和測試程式執行結束後的當下時間，兩個數值相減就是所要的。

實作方面，此暫存值紀錄在buffer state裡(下圖的inst count)，ELF裡的function call只是回傳那個暫存器的資料，實際上是由模擬器更新，也就是SPARC ISS每個cycle更新一次。



======================4/13============================

修改之前呈現的範例程式: 矩陣相乘
原本為了趕比賽把input data寫死在ELF裡，ELF sender把應用程式透過multi-core's interface把執行檔分給所有的core，不同的core自行取用運算所需的input，運算結果全部傳到其中一個core收集並結束。改成input & output data皆由ELF sender收送，core只負責收input和把運算結果output就好。

簡單的說就是需要外部module透過Multi-core’s Interface與core溝通的能力。我的想法是如同之前core之間的溝通方式；也就是增加與sc_port對應的I/O buffer，如同SPARC ISS的I/O buffer。Interface作資料讀寫看到的仍是buffers，並無多少改變。


這樣的好處是可以沿用舊有的溝通方式。不管是core還是sc_port，資料讀寫時看到的都是自己的I/O buffer，同樣interface在處理資料收送時，看到的同樣是buffers，整體上不會修改到太多。


之後還會加上別的功能如多個multi-core's interface的溝通，仍然是透過sc_port，所以應該也可以透過同樣的方式溝通。
======================3/28============================
比賽影片

比賽文件


上禮拜meeting時報告了幾個case執行的數據如下:
Case: 12X12矩陣相乘 分給四個core執行
total Instruction executed: 9,346,711 X 4
Time: 40.92 sec

Case: 12X12矩陣相乘 分給一個core執行
total Instruction executed: 34,639,538
Time: 55.29 sec

這數據蠻奇怪的，模擬34M指令需要55秒，模擬36M指令卻只要41秒?
因為明明是在同一台電腦上模擬，模擬四個core的效率竟然比一個core好。

後來找了很久才發現是systemc kernal的overhead問題，因為我的模擬器是這樣設計的，每跳一個clock所有的ISS就執行一個instruction，而模擬一個instruction的工作量比起systemc kernal小很多。也就是說模擬一個core就是每一個clock跑一個instruction和一次systemc kernal，模擬四個core就是每一個clock跑四個instruction和一個systemc kernal。

判斷這問題的方式則是增加每個instruction模擬的工作量即可，我的作法是加入很長的迴圈，之後得到的數據就比較正常了
Case: 12X12矩陣相乘 分給四個core執行
total Instruction executed: 4.2M X 4
Time: 502 sec

Case: 12X12矩陣相乘 分給一個core執行
total Instruction executed: 14.5M
Time: 436 sec


======================3/16============================

之前有提到，編譯應用程式ELF時裡面的I/O buffer的宣告和使用我是包成一個c library，使用者撰寫應用程式時必須include這個library，那麼編譯時如果有作最佳化是否會出問題？

答案是會的......

最後我避免的方式是加入attribute的設定，可以強制編譯器在處理這個function時使用指定的最佳化等級，譬如以下範例：
void foo () __attribute__ ((optimize(0)));
void foo () {
.........
}
表示foo()這個function編譯時強制使用optimization level 0，只是這方法只能在gcc上使用。

另外是把GDB的功能加到SPARC ISS上。使用ArchC產生SPARC ISS 時就有順帶產生SPARC GDB stub function，雖然ArchC文件寫GDB這段寫的不清不楚的，但是因為之前有作過8051 debugging stub，所以花了點時間trace code就知道怎麼用了。之後簡單測試了幾個指令：中斷點，單步執行，讀寫變數都沒有問題。



目前測試情況如上圖：左邊數來第一個視窗為systemC虛擬平台上兩個SPARC ISS，各一個GDB stub在跑，右邊兩個GDB視窗與之相連。由於systemc是單執行序的模擬方式，所以同時間只會有一個GDB端在與其對應的GDB stub溝通，其他的則是在等待狀態。

======================3/8============================

目前正在作多個SPARC ISS之間的資料讀寫問題，架構與溝通方式以下分段講解：
1.架構：一個中央模組ISS interface連接所有SPARC ISS，也就是全部透過sc_interface與ISS interface相連。每個SPARC ISS都會有I/O buffer各一個，和一個state buffer，ISS interface檢查每個SPARC ISS的I/O buffer並執行搬運資料的動作來達成。

那些buffer是SPARC ISS裡面執行的測試程式(test.elf)宣告在SPARC memory裡的。這裡就關係到應用程式設計者要怎麼使用I/O buffer來達成多核分工的問題。I/O buffer的宣告和使用我是包成一個c library，使用者撰寫應用程式時必須include這個library，並在程式一開始時呼叫buffer初始化的function。之後使用者就可以使用裡面的function進行多核之間的資料讀寫。

這裡比較麻煩的是buffer的位子，是由sparc gcc安排在 sparc memory，包在elf裡。因為ISS interface在存取I/O buffer時必須知道其位子，因此需要buffer初始化。

SPARC ISS載入elf後從pc = 0開始執行。elf裡一開始一定會執行buffer初始化，將I/O buffer address指定在幾個local register並等待(無限迴圈)ISS interface讀取。ISS interface讀取完後將建立一個I/O buffer address table，之後讀寫資料根據此table。ISS interface建立完table後告知SPARC ISS，跳脫等待的無限迴圈並結束buffer的初始化，之後就繼續執行elf的程式。



2. 溝通方式：假設有兩個SPARC ISS A&B，A寫資料給B，如上圖producer->consumer。
A將要寫的資料寫到自己的output buffer並註明目標為B
ISS interface檢查每個SPARC ISS的I/O buffer，知道A有資料要給B
ISS interface檢查B的input buffer是否為空
如果為空，將A的output buffer搬到B的input buffer
B檢查自己的input buffer是否為空以得知有沒有別人傳資料給他。

=====================================================
整個計畫的起始點是從一個單核SPARC simulator開始. 我找了很多模擬器, 最後決定用ArchC. ArchC為 Architecture Description Language, 我用ArchC產生SPARC V8 指令模擬器, 產生出來的模擬器是純c code, 包成一個SystemC module, 且支援gdb的樣子. 測試程式可以由sparc gcc編譯出的elf直接放到指令模擬器上執行.

有了SPARC ISS和其支援工具, 接下來是要發展成多核虛擬平台. 目的是可以將一個應用程式差成多個子程式, 放在不同的SPARC ISS上執行, 最後共同完成此應用程式的功能, 達到多核分工的目標.

System Architecture of ManyCore Simulatorn - 鈞/阿凡/宗胤/品皓

--- 2010/03/01 01:00PM ---

以下是 Y凡的意見，先將其放入主文。我在回應的地方後面有加一些意見。

-----------------------------------
關於core之間的通訊協定部分
我想參考TCP通訊協定，實做這些部分來達傳輸的可靠性，只是不知道這樣做對傳輸效率會有多大的影響

封包中主要定義"來源位址"、"目標位址"、"封包大小"、"剩餘window大小"、"資料sequence"、"偵錯資訊"及"要傳送的資料"

封包的遺失與重傳
設定一個delay time，當收方在收到封包後，送出ack給送方。
而送方在送出封包後，，開始計時，若在delay time前沒收到ack，就自動重送封包
根據收到ack的時間來動態的調整delay time

window advertisement
收送方兩端都約好一個空間大小作資料暫存，在傳送封包及ack時告知對方次空間的大小，當空間已滿時暫停傳送

3-way handshake
利用synchronization segment來建立連線，finish segment來終止連線

congestion control
送方送出封包收到ack後，即將資料傳輸量加倍，直到傳輸量達到收方的window size的一半為止

----------------------------------------------


--- 2009/12/02 06:40PM ---

實作方向

1. Using standard ANSI C to implement the loader's functions of processors(Cores) , so they can be cross-compiled to others binary code to run on different core architectures.
2. The Network-Interface and Router's functions are builded by SystemC. They simply do the function of exchanging data between processors(Cores) and Host.
3. The Network implementation should be easy replaced to the Network architecture, using in 8051 CPU, which suggested by 宗胤 today(2009/12/2).

Network Architecture(按我下載)

--- 2009/12/02 10:07AM ---

Function list of Host loader

1. Initialize all Processors, include the stack region size, data region size, number of code region , code region size.
2. Decide and Partion the Stack size, Data size, and function Code size according the Tasks of the Job.
3. Schedule the tasks of the job according the resource of multicore System.
4. Dispatch Data and tasks to Processor.
5. Infor Processor to execute a task.
6. Sync the task between all processor.
7. Deal with all errors and status of the multicore System.
8. Collect all the data from Processors and Finalize the Job.


Function list of Processor loader
1. Initialize the stack region size, data region size, number of code region , code region size.
2. Place the Code and Data to their local memory region.
3. Wait the command from Host to execute the code on code region.
4. Pass the data to next processor.
5. Pass the status to next processor.
6. Return data to Host.
7. Return status to Host.




--- 2009/12/01 ---

依據昨日晚上與今日下午與阿凡/宗胤/品皓討論出來的API架構

阿凡整理的API架構Word檔案(按此下載)

*********** 以下是直接節錄阿凡整理的檔案內容 ********
一開始在initial的動作中，會先將整個code與data分成幾段，並且知道每一段的大小，決定好每一個processor要執行哪些code，用到哪些code。

memory中包含幾個code region、幾個data region，以及這些region各自的起始位址及大小，每個processor會維護一個資料結構來存這些資訊。


HOST端
1.InitializeProcessor(ProcessorNo, Information)
將初始化資訊Information傳給指定的processor
2.DispatchCodeToProcessor(ProcessorNo, CodeNo , CodeRegionNo)
將指定的code傳遞至指定的processor的指定code region
3.StartExeCode(ProcessorNo, CodeRegionNo, RelativeStartEXEAddress)
processor開始執行指定位址的程式碼
4.DispatchDataToProcessor(ProcessorNo, DataNo, DataRegionNo)
將指定的data傳遞至指定的processor的指定data region
5.GetDataFromProcessor(ProcessorNo, DataRegionNo)
從指定的processor的指定data region取回資料
6. GetInformationFromProcessor(ProcessorNo, struct Information *)
從指定的processor取回region資訊
7.GetStatusFromProcessor(ProcessorNo, struct Status *)
從指定的processor取回Status資訊
8.定義region資訊
struct Information {
ProcessorNO; // 自己的processor號碼
NumOfCodeRegion; // CodeRegion數量
Struct CodeRegion *;
NumOfDataRegion; // DataRegion數量
Struct DataRegion *;
StackSize;
}
struct CodeRegion {
CodeNo;
CodeSize;
}
struct DataRegion {
DataNo;
DataSize;
}
9.定義status資訊
struct Status {
StatusNo;
}

Processor 端
1.Initialize(Information)
依照Information做初始化
2.ExeCode(CodeRegionNo)
執行指定code region裡的程式
3.InfoHost()
主動通知host，回傳Status
4.InfoProcessor(ProcessorNo, DataNo, DataRegionNo)
主動通知processor，回傳Status
5.SendDataToHost(DataRegionNo)
將指定data region裡的資料傳回host
6.SendDataToProcessor(ProcessorNo, DataNo, DataRegionNo)
將指定的data傳遞至指定的processor的指定data region
7.GetDataFromProcessor(ProcessorNo)
將指定的data傳遞至指定的processor的指定data region

Cloud Computing API
1.HostToProcesssor(Host, ProcessorNo, Data *)
2.ProcessorToHost(Host, ProcessorNo, Data *)
3.ProcesssorToProcesssor(ProcessorNo, ProcessorNo, Data *)




--- 2009/11/26 ---

補充一下昨日課堂上老師談論的一些資料

1. 系統的走向不以HPC為目標，但需兼顧日後的cores角色替換方便性。

2. 擔任cores的角色可以是硬體也可以是軟體。因此，它可以是arm base或8051或Sparc或x86等任一架構。

3. cores的任務很單純，就是接受host指示，執行由host送來的binary code。而且以single thread方式執行，但是其local memory可能同時間存放好幾套不同function的task的binary code，可以方便某一task執行完畢之後，切換至另一個task。

4. host 則是擔任資源與task分配的運籌中心角色。

5. 介於host與cores的網路，則以搭配的cores來對應軟硬體。可以是bus/ring等型式。



--- 2009/11/19 ---

依老師昨日所提，我大概畫了一下系統架構圖，如果有出入，請指正。
系統架構圖word檔案(按此下載)

至於所需的API，我先提出我想到的部分。

HOST Scheduler API
1. EXECodeToProcessor(ProcessorNo, CodeNo, CodeSize, CodeBlockNo )
2. ReplaceCodeFromProcessor((ProcessorNo, CodeNo)
3. DataToProcessor(ProcessorNo, DataNo, DataSize, DataBlockNo)
4. DataFromProcessor(ProcessorNo, DataNo, DataSize, DataBlockNo)
5. GetInformationFromProcessor(ProcessorNo, struct Information *)
6. struct Information {
ProcessorNO;
NumOfCodeBlock;
Struct CodeBlock *;
NumOfDataBlock;
Struct CodeBlock *;
}

Processor API
1. ExeCode(CodeBlockNo)
2. DataToHost(DataBlockNo)

Cloud Computing API
1. HostToProcesssor(Host, ProcessorNo, Data *)
2. ProcessorToHost(Host, ProcessorNo, Data *)

[轉錄] Gallery of Processor Cache Effects

分享一篇文章：Gallery of Processor Cache Effects

作者 Igor Ostrovsky 在  Microsoft Microsoft's Parallel Computing Platform team 服務。這篇文章透過 C# 七個實作來講述 Processor cache 的影響。測試程式簡短但切中要害，適合作為瞭解 cache 的入門。下面引用一些有趣的例子，希望勾起大家的興趣：

1. 下面的 code， loop1 和 loop2 的效能差異會是 1/16 嗎？
   

   int[] arr = new int[64 * 1024 * 1024];
   
   // Loop 1
   for (int i = 0; i < arr.Length; i++) arr[i] *= 3;
   
   // Loop 2
   for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

   
   



2. 下面的 code ，loop1 和 loop2 跑得一樣快嗎？
   
   
   
   

   int steps = 256 * 1024 * 1024;
   int[] a = new int[2];
   
   // Loop 1
   for (int i=0; i<steps; i++) { a[0]++; a[0]++; }
   
   // Loop 2
   for (int i=0; i<steps; i++) { a[0]++; a[1]++; }

   
   

一些外國鄉民的討論：http://www.reddit.com/r/programming/comments/ax1nv/gallery_of_processor_cache_effects/

P.S. 在 a 哥面前班門弄斧了!!

多核心8051與代理人伺服器

摘要

多核心處理器是目前最重要的研究議題之一，在未來要提高計算能力而同時不讓功率與散熱成為阻礙時，多核心處理器是解決方法之一，不過多核心處理器的開發不僅僅是硬體的問題，同時在系統設計以及軟體開發方面也具備多重困難。與其一開始就切入使用過於複雜的處理單元，本系統採用簡單的8051為基礎，經過適度的修改後，將多顆修改過的8051以晶片網路(Network on Chip-NoC)的方式連結起來，並且採用服務導向架構(Service Oriented Architecture-SOA)以及元件式軟體架構(Component Based Software Architecture-CBSA)的方式讓多顆8051可以共同運作並且為同一套應用軟體進行運算，我們使用代理人伺服器(Agent)負責將軟體元件的二元碼(Binary)透過元件快遞協定(Component Dispatch Protocol)傳送至多顆8051進行運算，而軟體元件之間所需要的資料交換則是利用我們所定義的元件資料交換協定(Component Data Exchange Protocol)透過晶片內網路進行傳輸，而運算的結果透過代理人/元件通訊協定(Agent Component Communication Protocol)，最重要的是，我們提供了包含以SystemC為基礎的電子系統層(Electronic System Level-ESL)的模擬器(Simulator)並執行在我們自行開發的開放原始碼的OpenESL發展平台之上，同時我們也提供了FPGA的實體模擬器(FPGA Emulator)，而代理人伺服器暫時是使用一部PC來取代。整體的成果呈現出一個簡單的多核心系統所應具備的基本功能，相信這是一個具體而微的展示，讓人可以看見(Visualize)未來真正功能強大的多核心系統，我們計畫在不久的未來採用更先進的處理器以及作業系統，讓多核心系統真正具備實用價值。

進度報告 Tilera64 - 品皓

這禮拜是報告關於multicore的架構，所以學長幫忙找了Tilera的網站。
由於我目前還沒有其spec書可以細讀，所以只能就我目前google到的做報告。

Tilera64，MIMD system，由8X8個tile組成
每個tile都是一個能獨立執行application的元件，
由一個32 bit RISC的core，加上cache和non-blocking switch組成。
interconnection是由iMesh的on-chip network處理。

星期二討論到的問題
Q: non-blocking switch是哪部份non-blocking? non-blocking遇到封包過多怎麼辦?
Q: 既然是MIMD，那需要一個master processor做管理，在哪裡?

投影片