并发性如何使Java代码可并行化？我如何使其可云化？

Question

我现在正在研究一个系统。这是一个复杂的系统，但它可以归结为一个Solver类，其方法如下：

public int solve(int problem); // returns the solution, or 0 if no solution found

现在，当系统启动并运行时，预计该方法的运行时间约为5秒，并且速度非常快。但是，我计划运行一些看起来有点像这样的测试：

List<Integer> problems = getProblems();
List<Integer> solutions = new ArrayList<Integer>(problems.size);
Solver solver = getSolver();
for (int problem: problems) {
    solutions.add(solver.solve(problem));
}
// see what percentage of solutions are zero
// get arithmetic mean of non-zero solutions
// etc etc

问题是我想在大量问题上运行它，不想永远等待结果。假设我有一百万个测试问题，我想在我泡一杯茶的时间内完成测试，我有两个问题：

1. 假设我有一个百万核处理器，Solver的实例是线程安全的，但没有锁定（它们是不可变的或其他），它们所做的所有计算都在内存中（即没有磁盘、网络或其他东西在进行）。我可以用线程安全列表替换解决方案列表，启动线程来解决每个问题，并期望它更快吗？要快多少？它能在5秒内运行吗

2. 有没有一个像样的Java云计算服务，我可以在那里购买500万秒的时间，并让代码在5秒内运行？我需要做什么来准备我的代码以便在这样的云上运行？500万秒到底要花多少钱

谢谢

Answer 1

使用合适的执行者。看看http://download.oracle.com/javase/6/docs/api/java/util/concurrent/Executors.html#newCachedThreadPool（）

Answer 2

你问的问题太大了。线程有开销，需要注意的一点是，它们在父进程中运行。如果你想同时运行一百万个这样的解算器，你就必须把它们分给它们自己的流程

Answer 3

您可以对每个输入使用一个程序，然后使用一个简单的批处理调度器，如Condor（用于Linux）或HPC（用于Windows）。你也可以在Amazon上运行它们，但是有一个学习曲线，它不仅仅是“上传Java代码&；go”

Answer 4

查看以下关于并发性的文章：

• http://www.vogella.de/articles/JavaConcurrency/article.html
• http://www.baptiste-wicht.com/2010/09/java-concurrency-part-7-executors-and-thread-pools/

基本上，Java7的新Fork/Join模型将非常适合这种方法。基本上，您可以设置数百万个以上的任务，并将它们尽可能分散到所有可用的处理器上。您必须提供自定义的“云”任务执行器，但这是可以做到的

当然，这是假设你的“求解”算法是完全并行的。简言之，只要解算器是完全自包含的，它们就应该能够在任意数量的处理器之间拆分

Answer 5

1. 当然，您可以使用标准工作线程范例来并行运行。但是会有一些同步开销（例如，当所有操作都试图同时完成时，对解决方案列表的更新将导致锁争用），因此它不会在5秒内运行。但它的速度将超过500万秒：-）
2. AmazonEC2每小时运行在0.085美元到0.68美元之间，这取决于您需要多少CPU（请参见pricing）。那么，大概120美元左右。当然，您需要设置一些单独的东西，以便在不同的CPU之间分配作业。一种选择可能是只使用Hadoop（请参见关于是否Hadoop is right for running simulations的问题）

你可以阅读像Guy Steele's talk on parallelism这样的文章来获得更多关于如何并行思考的信息

Answer 6

您已经用串行化的两个主要点表达了您的问题：问题产生和解决方案消耗（目前表示为整数列表）。您希望尽快得到第一个问题（目前，在所有问题产生之前，您不会得到它们）

我还假设问题列表顺序和解决方案列表顺序之间存在相关性，即solutions.get(3)是problems.get(3)的解决方案，这对于并行化来说是一个巨大的问题。你最好有一个Pair<P, S>的问题/解决方案，这样你就不需要保持相关性了

并行化求解器方法并不困难，但具体如何实现这一点在很大程度上取决于每个求解方法的计算成本（通常，方法越昂贵，并行化的开销越低，因此如果这些成本非常低，则需要对其进行批处理）。如果你最终得到一个分布式的解决方案，你当然会有更高的成本。Executor框架和fork/join扩展将是一个很好的起点