關鍵詞:機器人；乒乓效應；Cache中數據一致；互斥鎖機制

    唐俊奇（1967—）
男，工學學士，湄洲灣職業技術學院副教授、高級工程師，研究方向為計算機系統結構、計算機網絡。

    由于人工智能、計算機科學、傳感器技術及其它相關學科的長足進步，使得機器人的研究在高水平上進行，同時也為機器人控制器的性能提出更高的要求。由于機器人控制算法的復雜性以及機器人控制性能的亟待提高，許多學者從建模、算法等多方面進行了減少計算量的努力，但仍難以在串行結構控制器上滿足實時計算的要求。因此，必須從控制器本身 尋求解決辦法。其中最有效的方法就是采用多處理器作并行計算，提高 控制器的計算能力。如：有腿的步行機器人，其控制器采用多CPU(多處理機)結構(多處理機結構)控制方式[1]即：上、下位機二級分布式結構，上位機負責整個系統管理以及運動學計算、軌跡 規劃等。下位機由多個CPU(處理機)組成，每個CPU控制一個關節運動，這些CPU和主控機聯系是通過總線形式的緊耦合。這種結構的控制器工作速度和控制性能明顯提高。在該控制器中多處理機系統的性能則成為機器人運動的瓶頸。

    在下位機的多處理機系統中，每個處理機中都引入一獨立的Cache，由于Cache的引入縮短了訪存時間，減少互連網絡、存儲器的帶寬壓力和沖突，可以有效地克服了因多處理機系統性能所導致的瓶頸問題，但同時也產生了Cache中共享數據的一致性問題。為此本文著重闡述解決Cache中共享數據的一致性問題的方法。
　　
1 由CACHE數據導致機器人控制器性能降低的原因分析[2-6]

    有腿的步行機器人，其控制器采用多個CPU結構(多處理機結構)控制方式，在下位機的多個CPU(處理機)中，每個處理機控制一個關節運動。為了使高速緩存起到更大的作用，我們對現有協議中的并行算法要做一定的改動。比如，在數據項被訪問前就將一組數據項預先放入高速緩存的算法可以產生更高的性能。高速緩存的關鍵特性是以連續單元的塊的形式組成的。當處理器首次引用某個塊的一個或幾個字節后，這個塊的所有數據就會被傳送到高速緩存中。因此，如果引用這個塊中的其他數據時，該主存已在高速緩存中而不必從主存中調用它。如果高速緩存所使用的塊的大小和編譯器存儲數據的方法已知的話，并行算法就可以利用高速緩存的這一特性。當然，這種方法將大大地依賴于執行這個程序所使用的實際系統的情況。

圖 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.