Распараллеливание цикла for - PullRequest
25 голосов
/ 16 апреля 2011

У меня есть цикл for, где вычисления на итерации i не зависят от вычислений, выполненных в предыдущих итерациях.

Я хочу распараллелить цикл for (мой код в java), чтобы вычисление нескольких итераций могло выполняться одновременно на нескольких процессорах. Должен ли я создавать поток для вычисления каждой итерации, то есть количество создаваемых потоков равно количеству итераций (количество итераций в цикле for велико)? Как это сделать?

Ответы [ 4 ]

46 голосов
/ 16 апреля 2011

Вот небольшой пример, который может оказаться полезным для начала работы с распараллеливанием. Предполагается, что:

  1. Вы создаете Input объект, который содержит входные данные для каждой итерации вашего вычисления.
  2. Вы создаете объект Output, который содержит выходные данные вычисления входных данных каждой итерации.
  3. Вы хотите передать список входов и сразу получить список выходов.
  4. Ваш вклад - разумный кусок работы, поэтому накладные расходы не слишком велики.

Если ваши вычисления действительно просты, вы, вероятно, захотите рассмотреть их обработку в пакетном режиме. Вы можете сделать это, поставив скажем 100 в каждом входе. Он использует столько потоков, сколько имеется процессоров в вашей системе. Если вы имеете дело с задачами с исключительно интенсивным использованием процессора, то это, вероятно, тот номер, который вам нужен. Вы бы захотели подняться выше, если они заблокированы, ожидая чего-то другого (диск, сеть, база данных и т.

public List<Output> processInputs(List<Input> inputs)
        throws InterruptedException, ExecutionException {

    int threads = Runtime.getRuntime().availableProcessors();
    ExecutorService service = Executors.newFixedThreadPool(threads);

    List<Future<Output>> futures = new ArrayList<Future<Output>>();
    for (final Input input : inputs) {
        Callable<Output> callable = new Callable<Output>() {
            public Output call() throws Exception {
                Output output = new Output();
                // process your input here and compute the output
                return output;
            }
        };
        futures.add(service.submit(callable));
    }

    service.shutdown();

    List<Output> outputs = new ArrayList<Output>();
    for (Future<Output> future : futures) {
        outputs.add(future.get());
    }
    return outputs;
}
10 голосов
/ 16 апреля 2011

Вы не должны выполнять обработку потоков вручную.Вместо этого:

  • создайте службу исполнителя пула потоков разумного размера (если в ваших вычислениях нет операций ввода-вывода, используйте столько потоков, сколько у вас ядер).
  • Запустите цикл, который отправляет каждое отдельное вычисление в службу executor и сохраняет полученные Future объекты.Обратите внимание, что если каждое вычисление состоит из небольшого объема работы, это создаст много накладных расходов и, возможно, даже будет медленнее, чем однопоточная программа.В этом случае отправьте задания, которые выполняют пакеты вычислений, как подсказывает mdma.
  • Запустите второй цикл, который собирает результаты со всех Future s (он неявно будет ожидать завершения всех вычислений)
  • закрыть службу исполнителя
3 голосов
/ 16 апреля 2011

Нет, вы не должны создавать один поток для каждой итерации. Оптимальное количество потоков связано с количеством доступных процессоров - слишком много потоков, и вы тратите слишком много времени на переключение контекста без дополнительной производительности.

Если вы не полностью подключены к Java, вы можете попробовать параллельную высокопроизводительную систему C, такую ​​как OpenMPI. OpenMPI подходит для такого рода проблем.

0 голосов
/ 16 апреля 2011

Не создавайте темы самостоятельно.Я рекомендую вам использовать инфраструктуру fork / join (jsr166y) и создавать задачи, которые повторяются в заданном диапазоне элементов.Он позаботится об управлении потоками, используя столько потоков, сколько поддерживает оборудование.

Детализация задачи - главная проблема здесь.Если каждая итерация требует относительно небольшого количества вычислений (скажем, менее 100 операций), то выполнение каждой итерации как отдельной задачи приведет к большим накладным расходам планирования задач.Лучше, чтобы каждая задача принимала список аргументов для вычисления и возвращала результат в виде списка.Таким образом, вы можете заставить каждую задачу вычислять 1, 10 или тысячи элементов, чтобы поддерживать гранулярность задачи на разумном уровне, который балансирует поддержание доступности работы и снижает накладные расходы на управление задачами.

В jsr166z также есть класс ParallelArray., что позволяет повторять вычисления над массивом.Это может сработать для вас, если вычисляемые значения относятся к примитивным типам.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...