2

我编写了一个 java 程序来并行线性搜索算法，其中输入：100000 个随机数和 N = 线程数，其中每个线程采用 100000/N 个元素并执行线性搜索

我预计执行时间会随着 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);



  }
}
4

2 回答 2

3

The most likely reason for this is a decrease in cache performance.

Cache exploits locality of reference by reading ahead through the memory . The result of this process is that the cache has data that your program is going to request before your program requests it, improving the performance.

When your program searches at N addresses at the same time, cache tries to read ahead at all these locations. However, each thread has a much smaller number of items in cache, so the number of cache misses that need to be served at the same time goes up. Memory has limited bandwidth, so when one thread gets its cache filled, the remaining N-1 threads wait for memory, making no progress.

于 2016-04-13T10:50:50.203 回答
1

可能创建然后运行Threads比迭代100000 / N条目更耗时。尝试更大的输入。

如果迭代的100000 / N成本为K并且创建线程的成本为K + L，那么您创建的线程越多，运行程序的速度就越慢（|Number of Threads|*L更慢）。您可以尝试根据经验计算成本。

See Why is creating a Thread said to be expensive?

于 2016-04-13T10:42:12.887 回答