阶乘函数-并行处理 [英] factorial function - parallel processing
问题描述
我需要在EREW PRAM系统上的并行计算中编写阶乘函数(n!). 假设我们有n个处理程序. 复杂度应为log n. 我该怎么办?
i need to write factorial function(n!) in parallel computing on EREW PRAM system. assume that we have n proccessors. the complexity should be log n. how can i do this?
推荐答案
通常,您可以对N个处理器进行N次工作划分,并分别进行计算.您可以通过将每项工作的答案相乘来合并结果.例如第一个任务执行m !,下一个任务(2m)!/m !,第三个任务执行(3m!)/(2m!),等等.当您将结果相乘时,您将得到n!.
In general you can divide the work N times for N processors and compute each independently. You can combine the results by multiplying the answers for each piece of work. e.g. the first task performed m!, the next (2m)!/m!, the third (3m!)/(2m!) etc. When you multiple the results you get n!.
BTW:对于n
的较小值,例如小于1000,您将不会执行此操作,因为启动新线程/任务的开销可能大于在单个线程中执行此操作所花费的时间.
BTW: You wouldn't do this for small values of n
e.g less than 1000 because the overhead of starting new threads/task can be greater than the time it takes to do this in a single thread.
我怀疑伪代码是不够的,所以这里有个例子
I suspect pseudo code won't be enough so here is an example
public enum CalcFactorial {;
public static BigInteger factorial(long n) {
BigInteger result = BigInteger.ONE;
for (long i = 2; i <= n; i++)
result = result.multiply(BigInteger.valueOf(i));
return result;
}
public static BigInteger pfactorial(long n) {
int processors = Runtime.getRuntime().availableProcessors();
if (n < processors * 2)
return factorial(n);
long batchSize = (n + processors - 1) / processors;
ExecutorService service = Executors.newFixedThreadPool(processors);
try {
List<Future<BigInteger>> results = new ArrayList<Future<BigInteger>>();
for (long i = 1; i <= n; i += batchSize) {
final long start = i;
final long end = Math.min(n + 1, i + batchSize);
results.add(service.submit(new Callable<BigInteger>() {
@Override
public BigInteger call() throws Exception {
BigInteger n = BigInteger.valueOf(start);
for (long j = start + 1; j < end; j++)
n = n.multiply(BigInteger.valueOf(j));
return n;
}
}));
}
BigInteger result = BigInteger.ONE;
for (Future<BigInteger> future : results) {
result = result.multiply(future.get());
}
return result;
} catch (Exception e) {
throw new AssertionError(e);
} finally {
service.shutdown();
}
}
}
public class CalcFactorialTest {
@Test
public void testFactorial() {
final int tests = 200;
for (int i = 1; i <= tests; i++) {
BigInteger f1 = factorial(i * i);
BigInteger f2 = pfactorial(i * i);
assertEquals(f1, f2);
}
long start = System.nanoTime();
for (int i = 1; i <= tests; i++) {
BigInteger f1 = factorial(i * i);
}
long mid = System.nanoTime();
for (int i = 1; i <= tests; i++) {
BigInteger f2 = pfactorial(i * i);
}
long end = System.nanoTime();
System.out.printf("Single threaded took %.3f sec, multi-thread took %.3f%n",
(mid - start) / 1e9, (end - mid) / 1e9);
}
}
在3.72 GHz i7打印件上
on an 3.72 GHz i7 prints
Single threaded took 58.702 sec, multi-thread took 11.391
这篇关于阶乘函数-并行处理的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!