は私が 入力線形検索アルゴリズムを、paralleiseするJavaプログラムを書かれている多くの時間

Question

を消費します要素の数と線形検索を実行する

Nの増加に伴い実行時間が短縮されると予想されますが、実行時間は増加しています。

なぜですか？使用 モデル：CRCW共有メモリSIMDモデル

import java.io.*; 
import java.util.*; 
import java.util.Random; 

class data 
{ 
static int n; 
static int N; 
static int[] arr; 
static int result; 
static int eachProcSize; 
static int item; 
static void declare(int size,int noOfProcessors,int element) 
{ 
n=size; 
item=element; 
N=noOfProcessors; 
arr=new int[size]; 
eachProcSize=(int)Math.ceil((double)n/N); 
result=0; 
} 
} 


class sharedMemory 
{ 
static int n; 
static int ar[]; 
static int flag; 

static void declare(int size) 
{ 
n=size; 
ar=new int[n]; 
flag=0; 
} 
static synchronized void write(int index,int value) 
{ 
    ar[index]=value; 
} 
static synchronized void setFlag() 
{ 
flag=1; 
} 

} 
class monitorThread extends Thread 
{ 
int i; 
monitorThread(int index) 
{ 
i=index; 
} 
public void run() 
{ 
//if any processor has found element then it sets the flag 
if(sharedMemory.ar[i]==1) sharedMemory.setFlag(); 
} 
} 

class processor extends Thread 
{ 
int i; 
int size; 
int n=data.n; 
int N=data.eachProcSize; 
int[] arr; 

processor(int pos) 
{ 
i=pos; 
size=data.eachProcSize; 
arr=new int[size]; 
for(int j=0;j<size && (i*N+j)<n;j++) 
{ 
    arr[j]=data.arr[i*N+j]; 
} 

} 

public int linearSearch(int item, int[] list) { 

int i; 
for(i=0;i<list.length;i++) 
if(list[i]==item) return 1; 

return 0; 
} 


public void run() 
{ 
System.out.println("processor "+ i + " started and has started reading from "+ arr[0]) ; 



System.out.println("processor "+ i + " is performing linear search .."); 
if( linearSearch(data.item,arr)==1)sharedMemory.write(i,1); 
else sharedMemory.write(i,0); 
} 
} 



public class CRCW_SMSIMD_SEARCH{ 

public static void main(String args[]) 
{ 
Scanner in =new Scanner(System.in); 
int i,j,f=0; 

System.out.println("Enter no. of elements") ; 
int n=in.nextInt(); 

System.out.println("Enter no. of processors") ; 
int N=in.nextInt(); 

System.out.println("Enter the element you want to find.."); 
int item = in.nextInt(); 

data.declare(n,N,item); 

System.out.println("each proc size is"+ data.eachProcSize) ; 


//start time 



sharedMemory.declare(N); 

System.out.println(n+" elements are randomly generated :"); 

//random data generation 

    Random ran = new Random(); 
for(i=0;i<n;i++) 
    { 
     data.arr[i]=ran.nextInt(10000000); 
    } 



Thread t[]=new Thread[N]; 
System.out.println("starting "+N + " processors and reading data....\n"); 


//long start = System.currentTimeMillis(); 

for(i=0;i<N;i++) 
{ 

    t[i]=new processor(i); 

} 
    Thread[] monitor=new Thread[N]; 
    for(i=0;i<N;i++) 
    monitor[i]=new monitorThread(i); 

    long start = System.currentTimeMillis(); 

    for(i=0;i<N;i++) 
    t[i].start(); 



try{ 
    for(i=0;i<N;i++) 
    t[i].join(); 
    }catch(Exception e){e.printStackTrace(); } 




    for(i=0;i<N;i++) //continously monitor the shared memory to check if any processor has written 1; 
    monitor[i].start(); 


    long stop = System.currentTimeMillis(); 
    long timeTaken = stop- start; 


    if(sharedMemory.flag==1) 
    System.out.println("\nThe element was successfully found.."); 
    else 
    System.out.println("\nThe element was not found"); 

    System.out.println("\n\n time taken(in ms) by "+N+"processors is: "  +timeTaken); 



    } 
} 

Answer 1

を参照してください。

キャッシュは、メモリを先読みして参照のローカリティを利用します。このプロセスの結果、プログラムが要求する前にプログラムが要求するデータがキャッシュに格納され、パフォーマンスが向上します。

プログラムが同時にN個のアドレスを検索すると、キャッシュはこれらのすべての場所で先読みを試みます。しかし、各スレッドはキャッシュ内の項目数がはるかに少ないので、同時に処理する必要があるキャッシュミスの数が増えます。メモリには帯域幅が限られているため、あるスレッドがキャッシュをいっぱいにすると、残りのN-1スレッドはメモリを待って処理を進めません。

Answer 2

おそらく作成し、Threadsを実行する並列検索アルゴリズムは100000/Nエントリを反復処理よりも時間が高価です。より大きな入力を試してください。

100000/Nの繰り返し処理がKのコストを持っており、スレッドを作成すると、あなたのプログラムを（遅く|Number of Threads|*L）で実行されます遅くK + Lのコスト、作成した複数のスレッドがある場合。費用を経験的に計算しようとすることができます。

は、このための最も可能性の高い理由は、キャッシュ性能の低下であるWhy is creating a Thread said to be expensive?