Что-нибудь, что ДОЛЖНО быть сделано на многоядерном процессоре?

45

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

Что-нибудь нужно сделать на многоядерном процессоре?

Предположим, что для разработки и запуска есть бесконечное время.

Бен Легжеро
источник
8
Хотя ответы, приведенные ниже, в значительной степени кажутся «нет», исторически существуют системы, которые буквально не могли бы работать без сопроцессора, выполняющего некоторые задачи. Один из ярких примеров, которые я знаю, - это Nintendo DS, который включает 67-МГц процессор ARM9 и 33 МГц ARM7-процессор (также используется для бэк-компата при игре в GBA). Для игр DS, ARM7 управляет воспроизведением аудио и Wi-Fi, потому что ARM9 не может обрабатывать и выводить что-либо заметное на экран, не отставая от прямой передачи звука на звуковой чип. Так как @jmite утверждает, «при каких ограничениях», отсутствие скорости может потребовать нескольких процессоров.
Слипп Д. Томпсон
10
В моей работе мы используем многоядерные Xeon и расширения Linux для реального времени Xenomai для обработки аудио с малой задержкой. У нас есть трехступенчатый конвейер обработки звука, и каждый этап получает свое собственное выделенное ядро, которое использует ~ 70% циклов. Задачи не в реальном времени используют четвертое ядро, и любые циклы остаются на первых трех. Это было бы возможно только на одноядерном процессоре, если это одно ядро ​​было в 3 раза быстрее, чем ядро ​​на текущем 4-ядерном процессоре; учитывая, что текущий процессор работает на частоте 2 ГГц, этого может быть трудно достичь.
Джереми Фризнер
19
Программное обеспечение на одноядерном процессоре может эмулировать многоядерный процессор. Разница почти полностью в скорости.
user253751
24
Одна вещь, которая должна быть сделана в многоядерной системе, это тестирование многопоточного программного обеспечения. Потому что некоторые дефекты (почти) никогда не произойдут в одноядерной системе. Я не уверен, что это квалифицируется как ответ, хотя ...
nikie
13
@nikie Одноядерная система может эмулировать упорядочение памяти и устаревшие кэши - но я думаю, это было бы крайне неэффективно (например, замедление в 10 раз)
Nayuki

Ответы:

47

Если вас не волнует время работы, все, что вы можете сделать на многоядерном компьютере, вы можете сделать на одноядерном компьютере. Многоядерный компьютер - это просто способ ускорить некоторые виды вычислений.

TnTn

DW
источник
3
Я не совсем уверен, что это абсолютно правильно. Я не думаю, что ошибки согласованности памяти могут быть сгенерированы на одном ядре (да, можно было бы эмулировать систему с несколькими кэшами на одноядерном сервере, но такая косвенность является своего рода обманом). (Возможно, это эквивалентно внедрению регулярного обмена при перемещении операций в VLIW с использованием гарантированного || ism?) Я полагаю, что даже на однопоточном ядре все еще можно было бы извлечь энтропию из многопоточной изменчивости синхронизации, но количество энтропия будет меньше в единицу времени (что на самом деле просто вопрос производительности, как и другие различия).
Пол А. Клэйтон
6
@ PaulA.Clayton Ошибки согласованности памяти обычно нежелательны, и хорошо написанное программное обеспечение не должно их показывать. Однако, если вы действительно хотите, вы можете эмулировать их на одном процессоре. (Хотя это может быть медленно)
user253751
4
nn
11
«Одноядерный компьютер может эмулировать многоядерный компьютер с использованием разделения времени / времени». И действительно, сделали это с заре «современной» операционной системы.
Легкость гонок с Моникой
1
@ PaulA.Clayton Я думаю, что у вас могут возникнуть проблемы с согласованностью памяти (например, неатомарное приращение), если у вас будет два разных процесса, которые модифицируют одну и ту же разделяемую память. Вам просто нужно преимущественное многозадачность. Конечно, именно поэтому современные ОС не имеют процессов, совместно использующих одну и ту же доступную для записи память, если они явно не просят об этом.
Патрик М
58

Вопрос: при каких ограничениях?

Конечно, существуют проблемы, когда, если мы зададим вопрос «можем ли мы решить эту проблему на оборудовании X за заданный промежуток времени», ответ будет отрицательным.

Но это не «перспективный» ответ: вещи, которые в прошлом не могли быть выполнены достаточно быстро в одном ядре, вероятно, могут быть сейчас, и мы не можем предсказать, на что будет способно будущее оборудование.

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

С точки зрения графики, буквально все, что есть на GPU, может быть сделано на CPU ... если вы готовы ждать достаточно долго.

jmite
источник
3
@JanDvorak Я бы на самом деле сказал, что GPU этого не делает вообще;)
TomTom
15
Если время не является ограничением, вы можете выполнить все расчеты вручную, ручкой и бумагой.
mathreadler
2
@mathreadler Да, потому что мозг завершен по Тьюрингу. Что-то, что превратилось в длительные дебаты по обмену физическими стеками.
Дж.Бентли
4
На самом деле, @JanDvorak, генерируя VGA достаточно прост и может быть сделан в программном обеспечении на смиренные 16 МГц микроконтроллера, так как этот проект показывает: pyroelectro.com/tutorials/arduino_basic_vga
axello
3
@mathreadler Это на самом деле более сложный вопрос, чем кажется на первый взгляд. Короткий ответ может быть «да», потому что специализированная машина может сконструировать компьютер, не требуя для этого каких-либо инструментов. Более длинный ответ может быть «нет», потому что способность построить машину Тьюринга может подразумевать, что у нее есть более крупная машина Тьюринга, которая находится в состоянии «инициализации», где она создает остальную часть конечного автомата. Полный ответ еще сложнее, потому что мы никогда не создавали устройство Turing Complete. Мы разработали абстрактные идеи для машин, которые ...
Cort Ammon
17

Как указывали другие ответы, один ЦП всегда может эмулировать несколько ЦП, урезая время и играя роль каждого виртуального ЦП. Эта эмуляция, безусловно, рассчитает правильные ответы.

В реальном мире время выполнения может быть важным. Это может означать разницу между посредственной частотой кадров и звездным визуальным опытом. Или разница между прибылью и убытком в торговле.

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

Позвольте мне проиллюстрировать некоторые цифры. Предположим, у вас есть конвейер данных (3D-рендеринг и т. Д.), Который имеет 4 этапа обработки, каждый этап имеет 256 КБ программного кода, и у вас удобно 4 процессора с 256 КБ кэш-памяти L2. Если вы попытаетесь запустить эту обработку на одном процессоре, переключение между четырьмя задачами будет дорогостоящим и повлечет за собой большие потери в кеше. С другой стороны, если вы запускаете его в 4-х ядерной системе, вычисления потенциально могут быть очень плавными, пропуски кеша минимальны, а переключение контекста отсутствует. (Как примечание стороны, это связано с понятием закрепления определенных приложений на определенных ядрах - например, только выполнение операций ядра ОС в одном ядре или обработка TCP / IP и т. Д.)

Nayuki
источник
7

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

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

Фактически, если вы можете продемонстрировать, что ваш алгоритм может быть решен машиной Тьюринга (а это практически каждый алгоритм, который нас интересует), то можно доказать, что алгоритм может быть реализован не только одним ядром ЦП, но на самом деле конечный автомат с очень длинным куском ленты на память!

ШАХМАТЫ детектор гонки на самом деле использует это , чтобы найти случаи гонки. Он выполняет все однопоточные и систематически исследует все возможные чередования между потоками, пытаясь найти случаи, когда тест не пройден из-за гонки. CHESS зависит от того, что вы можете запустить любое многопоточное приложение на одном ядре.

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

Более экзотическая версия этого временного ограничения в системах реального времени. В некоторых жестких системах реального времени обслуживание прерываний является настолько сложным, что вам фактически приходится выбирать многоядерный процессор, который позволяет распределять прерывания по ядрам, или вы сталкиваетесь с ограничениями по времени.

Другое ограничение возникает с шинами данных. Рассмотрим Blue Gene / P в качестве примера. JUGENE, конкретный суперкомпьютер Blue Gene / P, имеет 144 терабайта памяти. Они просто не делают однопроцессорные компьютеры, которые могут получить доступ ко всей этой памяти.

Корт Аммон
источник
1
Re, они просто не делают однопроцессорные компьютеры, которые могут получить доступ к [так много] памяти. «Не» - это не то же самое, что «не могу». Вы можете спроектировать и построить однопроцессорный процессор с 144 или более терабайтами основной памяти. Единственная причина, по которой люди этого не делают, это из-за уменьшения отдачи: возрастающая практическая ценность добавления большего объема памяти к однопроцессорному дизайну достигает пика в какой-то момент, а затем падает по мере увеличения объема памяти, в то время как дополнительные затраты остаются постоянными. ,
Соломон Слоу
@jameslarge Вот почему это предложение появилось в той части моего ответа, в которой обсуждались реальные практические аппаратные средства, и почему оно не появилось в первых 2/3 ответа, в котором обсуждались теоретические возможности.
Cort Ammon
«Не» против «Не могу» иллюстрируется двумя системами в моем подвале. Если бы я мог физически добавить столько памяти в их аппаратные конфигурации, их процессоры «могли бы» получить доступ к каждому байту. Но я не могу, поэтому они "не могут". Возможности процессоров находятся за пределами практичности.
user2338816
Я думал что-то вроде этого ответа. Кажется, что условия гонки были бы невозможны (или бывали в 100% случаев) в одноядерной среде. Что касается практического применения, я предполагаю, что разработчик программного обеспечения мог бы разработать какую-то уникальную форму защиты от копирования путем кодирования некоторого странного теста состояния гонки, который всегда проходил бы на конкретном целевом оборудовании, но не давал бы работать на эмулируемом оборудовании, запущенном одним ядром. , В этом случае эмуляция многоядерной системой, вероятно, иногда проходит, но ненадежно.
Дэн Хендерсон
6

Если вам нужно наблюдать за процессом, выполняющимся на одном элементе обработки, не нарушая его поведение в реальном времени (или как можно меньше), например, для тестирования производительности или ведения журнала активности, вам, вероятно, понадобится отдельный ресурс обработки.

Ив Дауст
источник
Хороший, краткий пример чего-то, что потребовало бы точной эмуляции, если бы не несколько процессоров
Бен Легжеро
Эй, это твой аккаунт? Может, вы хотели бы слить это?
Зло
4

Другие ответы придерживаются ограниченного взгляда на параллелизм как «распределенный параллелизм». Это дает некоторые ответы: в чистой модели вычислений по Тьюрингу многоядерные процессоры не дают преимущества; единственное преимущество, которое вы можете получить, - это эффективность.

Существует в нескольких блоков обработки одна вещь (гной) может сделать один человек не может, хотя: выполнять операции параллельно , то есть в то же время .

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

Скажем, вам нужно обрабатывать данные датчика из нескольких источников в режиме реального времени. Что бы это ни значило точно в вашем приложении, один PU может обрабатывать только столько входных потоков одновременно, не нарушая ограничение по времени отклика. Таким образом, вам нужно несколько PU, если у вас слишком много датчиков для текущего поколения PU.

k

kkk

Рафаэль
источник
0

от CS pov, «многоядерный» в теории не сильно отличается от «распределенных вычислений». основная концепция - «независимые вычислительные элементы (которые вычисляются параллельно»), поэтому небольшая перефразировка вопроса («многоядерный» не совсем теоретическая концепция в CS) приводит к некоторым другим возможностям. как указано в других ответах, последовательное программирование эквивалентно параллельному программированию из CS pov. Это восходит к определению теоретической системы вычислений, а именно машины Тьюринга. Теоретический анализ производительности CS в конечном счете с точки зрения ТМ, где различие между параллельным и последовательным в действительности не применяется ( хотя есть и грубая аналогия с многолинейными ТМ ).

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

  • Учтите, что каждый процессор имеет независимую вероятность «[x]%» сбоя во время вычислений. Система может быть разработана таким образом, что посредством связи общая отказоустойчивость системы превосходит отдельные компоненты. это было применено много десятилетий назад, например, в системах космического челнока. в последнее время существуют базовые протоколы, разработанные для его использования, например, Paxos, которые решают так называемую проблему консенсуса . более практичным примером является Google, у которого есть множество запатентованных алгоритмов, по существу, создающих свои суперкомпьютер (ы) из индивидуально ненадежных элементов в сочетании с отказоустойчивыми алгоритмами.

  • Биткойн включает в себя распределенные транзакции для вычисления главной книги, и это не просто из-за проблем с нагрузкой при обработке. Алгоритм тщательно спроектирован, чтобы помешать поврежденным узлам. короче говоря, он «решает» / реализует проблему византийских генералов, которая заключается не только в максимизации параллельной производительности, она включает в себя независимые сущности, «проверяющие» друг друга и «алгоритмически / криптографически / надежно» отклоняющие неверные вычисления, что-то вроде «обмана» или «обмана» коррупция».

  • классический анализ параллелизма заключает, что существует около 7 «фундаментальных» типов шаблонов проблем, которые разлагаются на конкретные сбои параллельного выполнения. см. Исследование параллельных вычислений: взгляд из Беркли

  • Здесь есть некоторый элемент открытого теоретического вопроса, касающегося соображений производительности, рассмотренных в большинстве других ответов. Вопрос о том, существуют ли какие-либо проблемы, которые «по своей природе быстрее» параллельны, чем последовательные, также грубо известен как проблема P =? NC, где NC считается классом «эффективно распараллеливаемых» алгоритмов, а P - «эффективными [последовательными] алгоритмами». "

ВЗН
источник
1
Мне нравится этот ответ! Я многому научился на ваших примерах: D
Бен Легжеро
+1 за отказоустойчивость в критически важных средах с радиацией, -1 за отсутствие заглушек и избыточность.
Сис Тиммерман