Вопросы с тегом «parallel-computing»

Вопросы об алгоритмах или программах, выполняющих вычисления на нескольких процессорах одновременно. Не следует путать с параллельными или распределенными вычислениями!

68
Какая новинка в MapReduce?

Несколько лет назад MapReduce был провозглашен революцией в распределенном программировании. Также были критики но в целом был восторженный ажиотаж. Он даже запатентован! [1] Название напоминает mapи о reduceфункциональном программировании, но когда я читаю (Википедия) Шаг отображения: главный узел...

61
Распределенные и параллельные вычисления

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

44
Разница между параллельным и параллельным программированием?

При рассмотрении параллельного программирования обычно используются два термина: параллельный и параллельный. А некоторые языки программирования специально заявляют о поддержке параллельного программирования, например, Java . Означает ли это, что параллельное и параллельное программирование на...

28
Почему пустой тип C не аналогичен пустому / нижнему типу?

Википедия, а также другие источники, которые я обнаружил в списке voidтипа C как тип единицы, а не пустой тип. Мне кажется, что это сбивает с толку, так как мне кажется, что оно voidлучше подходит под определение пустого / нижнего типа voidНасколько я могу судить, ценности не обитают . Функция с...

24
Какие алгоритмы нельзя распараллелить?

Есть ли какой-нибудь алгоритм, который очень трудно распараллелить, или исследование все еще активно? Я хотел знать о любом алгоритме или любой области исследований в параллельных вычислениях. Все, что я искал, имеет «параллельную» реализацию. Просто хочу изучить некоторые неизученные области...

23
P-полнота и параллельные вычисления

Недавно я читал об алгоритмах проверки на сходство и читал, что проблема в P-полноте . Кроме того, следствием этого является то, что эта проблема или любая P-полная проблема вряд ли будут иметь эффективные параллельные алгоритмы. Какая интуиция стоит за этим последним утверждением?...

20
Как уменьшить параллельную сложность результатов до постоянного количества ядер?

У меня были проблемы с принятием теоретического представления о сложности «эффективно решаемого параллельным алгоритмом», которое задается классом NC : NC - это класс задач, которые могут быть решены параллельным алгоритмом за время на процессорах с .O ( журналсн )O(logc⁡n)O(\log^cn)c , k ∈ Np ( n...

20
Могут ли современные массивные параллельные процессоры эффективно управлять клеточными автоматами?

Интересно, достаточно ли хороши массивно-параллельные вычислительные блоки, предоставляемые в настоящее время в графических картах (например, программируемые в OpenCL ), чтобы эффективно моделировать одномерные клеточные автоматы (или, может быть, двумерные клеточные автоматы?). Если мы выберем...

18
Распараллеливание случайного чтения, кажется, работает хорошо - почему?

Рассмотрим следующую очень простую компьютерную программу: for i = 1 to n: y[i] = x[p[i]] Здесь и y - это n- элементные массивы байтов, а p - это n- элементный массив слов. Здесь n большое, например, n = 2 31 (так что только незначительная часть данных помещается в любой тип...

16
Как разница во времени выполнения задачи влияет на продолжительность работы?

Давайте предположим , что у нас есть большой набор задач τ1,τ2,...,τnτ1,τ2,...,τn\tau_1, \tau_2, ..., \tau_n и сборник идентичны (с точки зрения производительности процессоров) ρ1,ρ2,...,ρmρ1,ρ2,...,ρm\rho_1, \rho_2, ..., \rho_m которые работают полностью параллельно. Для интересующих нас сценариев...

14
Некоторые вопросы по параллельным вычислениям и классу NC

У меня есть ряд связанных вопросов по этим двум темам. Во- первых, большинство текстов сложности только замазывать класс NCNC\mathbb{NC} . Есть ли хороший ресурс, который более подробно освещает исследования? Например, то, что обсуждает все мои вопросы ниже. Кроме того, я предполагаю, что...

13
Зачем использовать SIMD, если у нас есть GPGPU?

Я думал, что этот вопрос лучше обслуживать в CS-части Stack Exchange. Теперь, когда у нас есть GPGPU с такими языками, как CUDA и OpenCL, мультимедийные расширения SIMD (SSE / AVX / NEON) все еще служат цели? Недавно я прочитал статью о том, как можно использовать инструкции SSE для ускорения...

13
Получение параллельных элементов в разрешении зависимостей

Я реализовал топологическую сортировку на основе статьи в Википедии, которую я использую для разрешения зависимостей, но она возвращает линейный список. Какой алгоритм я могу использовать, чтобы найти независимые...

12
Multicore SAT Solver

Я пытаюсь решить проблему SAT переменных 25k пунктов 5k переменных. Так как он работал в течение часа (precosat), и я хотел бы потом решить более крупные, я ищу многоядерный SAT-Solver. Кажется, что есть много SAT-Solvers, я совершенно потерян. Кто-нибудь может указать мне лучший вариант для моего...

11
Параллельный алгоритм нахождения максимума за времени с использованием процессоров

Мы были представлены в классе с алгоритмом нахождения максимума в массиве параллельно в временной сложности с компьютерами.O(1)O(1)O(1)n2n2n^2 Алгоритм был: Дан массив A длины n: Создайте массив флагов B длиной n и инициализируйте его нулями с компьютерами.nnn Сравните каждые 2 элемента и напишите...

11
Существуют ли параллельные матричные алгоритмы возведения в степень, которые более эффективны, чем последовательное умножение?

Требуется найти степень (целое положительное число) матрицы действительных чисел. Существует множество эффективных алгоритмов умножения матриц (например, некоторые параллельные алгоритмы - Кэннона, DNS ), но существуют ли алгоритмы, предназначенные именно для определения мощности матрицы и более...

10
Почему сравнения на GPU так дороги?

Пытаясь улучшить производительность моего класса обнаружения столкновений, я обнаружил, что ~ 80% времени, проведенного в графическом процессоре, тратится на условия if / else, просто пытающиеся определить границы для сегментов, через которые он должен проходить. Точнее: каждый поток получает...

9
Может ли алгоритм искусственной нейронной сети быть выражен в терминах операций сокращения карт?

Может ли алгоритм искусственной нейронной сети быть выражен в терминах операций сокращения карт? Мне также более интересны методы распараллеливания применительно к ANN и их применение в облачных вычислениях. Я бы подумал, что один подход будет включать в себя запуск полной ANN на каждом узле и...

9
Могут ли объединения быть распараллелены?

Предположим, мы хотим объединить два отношения в предикате. Это в NC? Я понимаю, что доказательство того, что он не находится в NC, будет равносильно доказательству того, что п≠ NСп≠NСP\not=NC , поэтому я бы принял доказательство того, что это открытая проблема, в качестве ответа. Меня интересует...

9
Каково текущее состояние параллельных или параллельных программ в изоморфизме Карри-Ховарда?

В « Доказательствах и типах» Жирара мы можем прочитать: С алгоритмической точки зрения, секвенциальное исчисление не имеет изоморфизма Карри-Ховарда из-за множества способов написания одного и того же доказательства. Это мешает нам использовать его в качестве типизированного исчисления, хотя мы...