在 JAVA 中创建更多线程来并行化线性搜索会消耗更多时间

Question

我写了一个 java 程序来并行化线性搜索算法，其中 input:100000 随机数和 N=线程数，其中每个线程获取 100000/N 个元素并执行线性搜索

我预计执行时间会随着 N 的增加而减少，但执行时间却在增加！

为什么？模型 used:PARALLEL 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

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

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

见Why is creating a Thread said to be expensive?

Answer 2

最可能的原因是缓存性能下降。

缓存通过内存提前读取来利用引用的局部性。这个过程的结果是缓存在你的程序请求它之前就拥有了你的程序要请求的数据，从而提高了性能。

当您的程序同时搜索 N 个地址时，缓存会尝试在所有这些位置进行预读。但是，每个线程在缓存中的项目数量要少得多，因此需要同时处理的缓存未命中数会增加。内存带宽有限，所以当一个线程的缓存被填满时，剩下的 N-1 个线程等待内存，没有任何进展。

在 JAVA 中创建更多线程来并行化线性搜索会消耗更多时间

creating more threads in JAVA to parallelize linear search consumes more time

java

parallel-processing

multithreading

linear-search