我需要在 EREW PRAM 系统上的并行计算中编写阶乘函数(n!) 。假设我们有 n 个处理器。复杂度应该是 log n。我怎样才能做到这一点?
问问题
2600 次
2 回答
2
我们有 n 个处理器。复杂度应该是 log n。
这个问题没有意义,因为您正在寻找一种算法,其复杂性 ( log n
)会随着您添加处理器(即增加n
)而增加。
我猜你要做的是将产品1*2*3*...*k
分成n
大小相等的块,在单独的处理器上计算每个子产品,然后将n
结果相乘。
于 2012-05-06T09:44:11.173 回答
2
一般来说,您可以为 N 个处理器划分 N 次工作并独立计算每个。您可以通过将每件作品的答案相乘来组合结果。例如,第一个任务执行了 m!,下一个 (2m)!/m!,第三个 (3m!)/(2m!) 等等。当你将结果乘以你得到 n!。
顺便说一句:对于小于 1000 的小值,您不会这样做,n
因为启动新线程/任务的开销可能大于在单个线程中执行此操作所需的时间。
我怀疑伪代码还不够,所以这里有一个例子
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 上打印
Single threaded took 58.702 sec, multi-thread took 11.391
于 2012-05-06T09:56:58.843 回答