今日頭條
官方微信
官方抖音
案例頻道
關鍵詞:機器人；乒乓效應；Cache中數據一致；互斥鎖機制
唐俊奇（1967—）
男，工學學士，湄洲灣職業技術學院副教授、高級工程師，研究方向為計算機系統結構、計算機網絡。
由于人工智能、計算機科學、傳感器技術及其它相關學科的長足進步，使得機器人的研究在高水平上進行，同時也為機器人控制器的性能提出更高的要求。由于機器人控制算法的復雜性以及機器人控制性能的亟待提高，許多學者從建模、算法等多方面進行了減少計算量的努力，但仍難以在串行結構控制器上滿足實時計算的要求。因此，必須從控制器本身 尋求解決辦法。其中最有效的方法就是采用多處理器作并行計算，提高 控制器的計算能力。如：有腿的步行機器人，其控制器采用多CPU(多處理機)結構(多處理機結構)控制方式[1]即：上、下位機二級分布式結構，上位機負責整個系統管理以及運動學計算、軌跡 規劃等。下位機由多個CPU(處理機)組成，每個CPU控制一個關節運動，這些CPU和主控機聯系是通過總線形式的緊耦合。這種結構的控制器工作速度和控制性能明顯提高。在該控制器中多處理機系統的性能則成為機器人運動的瓶頸。
在下位機的多處理機系統中，每個處理機中都引入一獨立的Cache，由于Cache的引入縮短了訪存時間，減少互連網絡、存儲器的帶寬壓力和沖突，可以有效地克服了因多處理機系統性能所導致的瓶頸問題，但同時也產生了Cache中共享數據的一致性問題。為此本文著重闡述解決Cache中共享數據的一致性問題的方法。
1 由CACHE數據導致機器人控制器性能降低的原因分析[2-6]
有腿的步行機器人，其控制器采用多個CPU結構(多處理機結構)控制方式，在下位機的多個CPU(處理機)中，每個處理機控制一個關節運動。為了使高速緩存起到更大的作用，我們對現有協議中的并行算法要做一定的改動。比如，在數據項被訪問前就將一組數據項預先放入高速緩存的算法可以產生更高的性能。高速緩存的關鍵特性是以連續單元的塊的形式組成的。當處理器首次引用某個塊的一個或幾個字節后，這個塊的所有數據就會被傳送到高速緩存中。因此，如果引用這個塊中的其他數據時，該主存已在高速緩存中而不必從主存中調用它。如果高速緩存所使用的塊的大小和編譯器存儲數據的方法已知的話，并行算法就可以利用高速緩存的這一特性。當然，這種方法將大大地依賴于執行這個程序所使用的實際系統的情況。
圖1 高速緩存中假共享
之所以要在高速緩存中使用塊的原因是：順序程序的基本特性和引用的時間局部性(temporal locality)(也就是說存儲器引用傾向于接近以前存儲器引用)。在多處理機系統的高速緩存中使用連續單元塊的主要缺點是：在多處理機系統中，不同的處理器可能需要同一個主存塊的不同部分而不是相同的字節。盡管實際數據不共享，但如果一個處理器對該塊的其他部分寫入，則這個塊在其他高速緩存上的拷貝就要全部地進行更新或者使無效。這就是所謂的假共享(false sharing)，它對系統的性能有負面的影響。圖1展示了假共享。在圖1中，一個塊由8個字組成，從0到7。兩個處理器訪問同一塊但不同部分(處理器1訪問字3，而處理器2訪問字5)。假設處理器1寫了字3，則高速緩存一致協議將更新或者使處理器2中的高速緩存塊無效，即便處理器2永遠也不訪問3。假設現在處理器2又改動了字5，則高速緩存一致協議反過來又要將處理器1中的高速緩存塊進行更新或者使無效，而處理器1也許也永遠不會訪問字5。這樣下去，就會導致高速緩存塊的乒乓效應(ping-ponging)。從而降低了控制器的計算能力。
2 Cache中數據一致性問題的解決方法
從硬件的角度來看：現有兩種解決Cache一致性硬件算法，但是都存在各自的問題：一是基于共享總線的多處理機系統監視(Snoopy)協議，這種算法在處理機數目較多時，總線的負載壓力過大它將成為整個系統的瓶頸。另一種硬件算法為目錄表法，這種算法使得存儲器開銷大;實現一致性時，延盡時間較長;而且擴展能力也差。隨著系統中處理機數目的增加和多處理機系統的發展，硬件算法更加顯示出其缺點和局限性。這樣的系統難以保證機器人在高速運動中所要求的精度指標。我們必須尋找一個新的路徑以滿足現實需求。
2.1 編譯時設置用基于訪存時標使Cache中數據一致
基于訪存時標的方法這種方法的基本思想是每一共享數據都帶有一時鐘標計，而Cache中的每一字(一塊)，以及讀寫訪存也都帶有一時鐘標計。若Cache中的一字被修改一次，則字的時鐘加1，當對Cache中的一字進行訪問時，若訪問時標大于或等于Cache中字的時標，說明訪問的是最新版本，否則訪問主存，例如:
/*LOOPiL*/
Doall i1=1 ,n1
.
.
X(f0)
.
.
end doall
.
.
/* LOOPi3 */
Doall i3=1,n3
.
.
.... X(p0)
.
.
end doall
程序中的數組X有一時鐘，其初始值為0，在LOOPi1;，之后，X的時鐘為1，經LOOPi2;之后，X的時鐘為2。在LOOPi3;,中，若Cache中X的時鐘標計為0或為1，則說明不是最新版本，若為2，則說明Cache中的數據有效。
基于訪存時標的方法，借用了流分析訪存標志法的思想但是它在更復雜分析的基礎上，引入動態成份—時標使之在一定程度上使失效的選擇性更加充分，提高了效率。
2.2 使用互斥鎖機制避免假共享產生[2-6]
有腿的步行機器人的下位機由多個CPU(處理機)組成，每個CPU控制一個關節運動，可以創建n個線程與之對應。為了便于分析，避開機器人關節運動的復雜性，而以對數組a[1000]求和這個簡單的例子來進行說明如何避免共享存儲器sum的乒乓效應。
在此筆者將創建n個線程，每個線程都要重復地從列表中獲取元素并加到它們的和中。當所以的元素都被取走后這些線程就將它的部分和加到共享單元sum中，如下程序是按照圖4所示的結構創建共享數據。各個線程通過共享單元global_index獲取a[ ]數組的下一個未加元素。在這個index所指的數組元素被讀后，index就會加1，從而指向下一個未加元素，為下一次元素的獲取做好準備。結果所在的主存單元將sum，并將同樣被共享且使用鎖機制來保護對其的訪問。
有一點非常重要，那就是不能在臨界段外訪問全局下標gloabnl_index。這包括察看下標是否達到最大值的操作。如下語句：
while (global_index< array_aize)……
需要訪問global_index,在while內的語句體已經被執行之前，這個下標可能被其他的線程改變。在本代碼中，使用一個局部變量，local_indexgo 存放當前讀到global_index的值，以便更新部分和以及檢查下標是否達到了最大值。
圖 2 在互斥鎖機制中同時使用sum和global_index共享存儲單元
在本代碼中，使用了互斥鎖機制，而沒有使用條件變量。使用該方法的程序如下：
# include < stdio.h>
# include < pthread.h>
# include arrau_size 1000
# include no_threads 10 /* shared data */
int a[array_size]; /* array of numbers to sum */
int global_index =0; /* global index */
int sum =0; /* final result,also used by slaves */
pthread_mutex_t mutex1;
void * slave(void * ignored){ /* slave threads */
int local_index,partial_sum =0;
do ｛ /* get next index into the array */
pthread_mutex_lock(&mutex1);
/* read current index & save locally */
local_index = clobal_index;
global_index ++;
/* increment clobal index */
pthread_mutex_unlock(& mutexl);
if (local_index<array_size)
partial_sum += * (a+local_index);
｝while(local_index<array_size);
pthread_mutex_lock(&mutexl);
/* add partial sum global sum */
sum += partial_sum;
pthread_mutex_unlock (& mutexl);
return( ); } /* Thread exits */
main ( ) ｛
int i;
pthread_t thread[no_threads]; /* threads */
pthread_mutex_init(& mutexl,NULL);
/* initialize mutex */
for ( i=0; i<array_size; i++) / * initialize [] */
a[i]=i+1;
for (i=0;i<no_threads; i++)
/* initialize a[] */
if(pthread_create(&thread [i],NULL,slave ,NULL) !=0)
perror(“pthread_create fails”);
for (i=0;i<no_threads; i++) /* join threads */
if (pthread__join(thread [i],NULL !=0)
perror(“pthread_join fails”);
printf(“The sum of 1 to *i is &d\n”,array_size,sum);｝ /* end of main */
SAMPLE OUTPUT
The sum of 1 to 1000 is 500500
2.3 用Java監控程序的方法避免假共享產生[4]
在Java中有監控程序的概念。Java中的關鍵詞Synchronized可以使方法中的一段代碼成為線程安全的，它可防止多個線程間的沖突。
仍以對數組a[1000]求和為例，在編程時采用動態平衡的方法來負責任務的分配，下面是利用JAVA監控程序以避免共享存儲器sum的乒乓效應用于Java的監控程序方法(利用該Java監控程序實現：一個線程承擔所有的工作)。
public class Adder ｛
public int[] array;
private int sum =0;
private int index =0;
private int number_of_threads =10;
private int threads_quit;
public Adder( ) ｛
threads_quit =0;
array =new int [1000];
initializeArray ( );
startThreads ( ); ｝
public synchronized int getNextIndex ()｛
if (index<1000) return(index++);
else
return(-1); ｝
public synchronized void addpartialsum(int partial_sum) ｛
sum=sum + partial_sum;
if(++ threads_quit = = number_of_threads)
System.out.println(“The sum of numbers is ”+sum); ｝
private void initializeArray () ｛
int i;
for(i=0; i<1000, i++) array (i) =i; ｝
public void startThreads ( ) ｛
int i=0;
for (i=0;i<10;i++) ｛
AdderThread at = new AdderThread(this,i); ｝｝
public static void main (String arge[ ]) ｛
Adder a= new Adder ( ); ｝｝
class AdderThead extends Thread
｛
int partial_sum =0;
Adder parent;
Int number;
public AdderThread(Adder parent, int number)
｛ this.parent=parmet;
this.number=number; ｝
public void run ( ) ｝
int index=0;
while (index !=-1)｛
partial_sum=partial_sum + parent.array[index];
index=parent.getNextIndex( ); ｝
system.out.println(“partial sum from thread”+ number +”is”
+ partial_sum);
parent.addpartialSum(partial_sum);}}
3 結束語
仿真實驗表明：有腿的步行機器人，在其下位機的多處理機系統中，由于采用了編譯時設置用基于訪存時標、互斥鎖機制、Java監控程序這些方法使Cache中數據保持一致，充分發揮了Cache的優點縮短了訪存時間，減少互連網絡、存儲器的帶寬壓力和沖突，有效地克服了因多處理機系統性能所導致的瓶頸問題，從而提高了機器人多處理器計算機系統的性能。
參考文獻：
[1]普杰信，嚴學高.機器人分布式計算機控制系統結構的性能分析[J].機器人,1994,16(3)144-149.
[2]唐俊奇.多處理機系統Cache共享數據乒乓效應的研究[J].莆田學院學報，2006，13（2）51-54.
[3]孫強南，孫昱東等編著.計算機系統結構[M].北京：科學出版社，2000.
[4]殷兆麟.Java語言程序設計[M].北京：高等教育出版社，2002.
[5]TMASEVIC M., AND V.MILUTINOVIC(1993),The Cache CoherenceProblem in Shard-Memory Multiprocessor:Hardware Solutions, IEEE CS Press,Los Alamitos,California.
[6]薛燕,樊曉椏,李瑛. 多處理機系統中數據Cache的一種優化設計[J].微電子學與計算機，2004，21（12），191-194.
北京市公安局海淀分局備案號：11010802023656號