Обсуждая, насколько многопоточной должна быть наша программа, моя команда ломала голову над тем, есть ли что-то, что абсолютно невозможно сделать на одноядерном процессоре. Я утверждал, что обработка графики требует массовой параллельной обработки, но они утверждают, что такие вещи, как DOOM, были выполнены на одноядерных процессорах без графических процессоров.
Что-нибудь нужно сделать на многоядерном процессоре?
Предположим, что для разработки и запуска есть бесконечное время.
computation-models
cpu
multi-tasking
Бен Легжеро
источник
источник
Ответы:
Если вас не волнует время работы, все, что вы можете сделать на многоядерном компьютере, вы можете сделать на одноядерном компьютере. Многоядерный компьютер - это просто способ ускорить некоторые виды вычислений.
источник
Вопрос: при каких ограничениях?
Конечно, существуют проблемы, когда, если мы зададим вопрос «можем ли мы решить эту проблему на оборудовании X за заданный промежуток времени», ответ будет отрицательным.
Но это не «перспективный» ответ: вещи, которые в прошлом не могли быть выполнены достаточно быстро в одном ядре, вероятно, могут быть сейчас, и мы не можем предсказать, на что будет способно будущее оборудование.
Что касается вычислимости, мы знаем, что одноленточная машина Тьюринга способна выполнять все те же функции, что и одноядерный или многоядерный компьютер, поэтому, за исключением времени выполнения, нет проблем, которые многоядерный компьютер может решить, одноядерный не может.
С точки зрения графики, буквально все, что есть на GPU, может быть сделано на CPU ... если вы готовы ждать достаточно долго.
источник
Как указывали другие ответы, один ЦП всегда может эмулировать несколько ЦП, урезая время и играя роль каждого виртуального ЦП. Эта эмуляция, безусловно, рассчитает правильные ответы.
В реальном мире время выполнения может быть важным. Это может означать разницу между посредственной частотой кадров и звездным визуальным опытом. Или разница между прибылью и убытком в торговле.
Одна патологическая ситуация, когда мультипроцессор намного быстрее, чем однопроцессорный, - это когда обработка представляет собой конвейер данных, переключение контекста обходится дорого, а машинный код для каждой стадии конвейера едва помещается в кэш ЦП.
Позвольте мне проиллюстрировать некоторые цифры. Предположим, у вас есть конвейер данных (3D-рендеринг и т. Д.), Который имеет 4 этапа обработки, каждый этап имеет 256 КБ программного кода, и у вас удобно 4 процессора с 256 КБ кэш-памяти L2. Если вы попытаетесь запустить эту обработку на одном процессоре, переключение между четырьмя задачами будет дорогостоящим и повлечет за собой большие потери в кеше. С другой стороны, если вы запускаете его в 4-х ядерной системе, вычисления потенциально могут быть очень плавными, пропуски кеша минимальны, а переключение контекста отсутствует. (Как примечание стороны, это связано с понятием закрепления определенных приложений на определенных ядрах - например, только выполнение операций ядра ОС в одном ядре или обработка TCP / IP и т. Д.)
источник
Гораздо сложнее разработать действительно гнусные гонки данных с одним процессором. Я имею в виду, конечно, вы можете выполнить разрыв между словами, если прервете один процессор, но можете ли вы создать экзотические сценарии, где нет единственного чередования потоков, которое делает то, что вы хотите?
Ладно, возможно, коварные ошибки не считаются правильным использованием нескольких кодов. Как оказалось, многоядерный процессор не может сделать то, что одно ядро не может дать за это время. Причина проста. Если вы пытаетесь избежать этих злых гонок данных, в вашем коде должны быть точки синхронизации. Если вы моделируете свой код как решетку вычислений, в которой входные данные должны быть завершены и синхронизированы, прежде чем вы сможете рассчитывать и производить выходные данные, легко заметить, что один ЦП может просто продвигаться по решетке, вычисляя следующий доступный блок работы ,
Фактически, если вы можете продемонстрировать, что ваш алгоритм может быть решен машиной Тьюринга (а это практически каждый алгоритм, который нас интересует), то можно доказать, что алгоритм может быть реализован не только одним ядром ЦП, но на самом деле конечный автомат с очень длинным куском ленты на память!
ШАХМАТЫ детектор гонки на самом деле использует это , чтобы найти случаи гонки. Он выполняет все однопоточные и систематически исследует все возможные чередования между потоками, пытаясь найти случаи, когда тест не пройден из-за гонки. CHESS зависит от того, что вы можете запустить любое многопоточное приложение на одном ядре.
Случаи, когда вам нужен многоядерный, появляются, когда вы начинаете расширять пределы аппаратного обеспечения. Очевидный - когда у вас есть ограничения по времени. Некоторые проблемы с ограничениями в реальном времени невозможно сделать с одним ядром, потому что они просто не могут управлять часами одного ядра достаточно быстро. Есть причина, по которой процессоры поднялись до 4 ГГц, а затем немного успокоились, предпочитая больше ядер на более низких скоростях.
Более экзотическая версия этого временного ограничения в системах реального времени. В некоторых жестких системах реального времени обслуживание прерываний является настолько сложным, что вам фактически приходится выбирать многоядерный процессор, который позволяет распределять прерывания по ядрам, или вы сталкиваетесь с ограничениями по времени.
Другое ограничение возникает с шинами данных. Рассмотрим Blue Gene / P в качестве примера. JUGENE, конкретный суперкомпьютер Blue Gene / P, имеет 144 терабайта памяти. Они просто не делают однопроцессорные компьютеры, которые могут получить доступ ко всей этой памяти.
источник
Если вам нужно наблюдать за процессом, выполняющимся на одном элементе обработки, не нарушая его поведение в реальном времени (или как можно меньше), например, для тестирования производительности или ведения журнала активности, вам, вероятно, понадобится отдельный ресурс обработки.
источник
Другие ответы придерживаются ограниченного взгляда на параллелизм как «распределенный параллелизм». Это дает некоторые ответы: в чистой модели вычислений по Тьюрингу многоядерные процессоры не дают преимущества; единственное преимущество, которое вы можете получить, - это эффективность.
Существует в нескольких блоков обработки одна вещь (гной) может сделать один человек не может, хотя: выполнять операции параллельно , то есть в то же время .
Это очень полезно, если вы запускаете несколько программ одновременно. Конечно, очень редко вам просто нужно больше, чем одновременное выполнение, и большинство применений сводятся к повышению эффективности. Но есть эта разница.
Скажем, вам нужно обрабатывать данные датчика из нескольких источников в режиме реального времени. Что бы это ни значило точно в вашем приложении, один PU может обрабатывать только столько входных потоков одновременно, не нарушая ограничение по времени отклика. Таким образом, вам нужно несколько PU, если у вас слишком много датчиков для текущего поколения PU.
источник
от CS pov, «многоядерный» в теории не сильно отличается от «распределенных вычислений». основная концепция - «независимые вычислительные элементы (которые вычисляются параллельно»), поэтому небольшая перефразировка вопроса («многоядерный» не совсем теоретическая концепция в CS) приводит к некоторым другим возможностям. как указано в других ответах, последовательное программирование эквивалентно параллельному программированию из CS pov. Это восходит к определению теоретической системы вычислений, а именно машины Тьюринга. Теоретический анализ производительности CS в конечном счете с точки зрения ТМ, где различие между параллельным и последовательным в действительности не применяется ( хотя есть и грубая аналогия с многолинейными ТМ ).
но, рассматривая этот вопрос менее абстрактно, распределенные вычисления действительно лучше или, возможно, даже необходимы для некоторых проблем, связанных с отказоустойчивостью . в этой области есть концепция, которая применяется, когда / где независимые вычислительные элементы взяты, чтобы иметь некоторую степень ненадежности (это на самом деле не является универсально применимым допущением для всех контекстов). Вот несколько случаев, когда отказоустойчивость повышается с помощью или даже требует независимых вычислительных элементов.
Учтите, что каждый процессор имеет независимую вероятность «[x]%» сбоя во время вычислений. Система может быть разработана таким образом, что посредством связи общая отказоустойчивость системы превосходит отдельные компоненты. это было применено много десятилетий назад, например, в системах космического челнока. в последнее время существуют базовые протоколы, разработанные для его использования, например, Paxos, которые решают так называемую проблему консенсуса . более практичным примером является Google, у которого есть множество запатентованных алгоритмов, по существу, создающих свои суперкомпьютер (ы) из индивидуально ненадежных элементов в сочетании с отказоустойчивыми алгоритмами.
Биткойн включает в себя распределенные транзакции для вычисления главной книги, и это не просто из-за проблем с нагрузкой при обработке. Алгоритм тщательно спроектирован, чтобы помешать поврежденным узлам. короче говоря, он «решает» / реализует проблему византийских генералов, которая заключается не только в максимизации параллельной производительности, она включает в себя независимые сущности, «проверяющие» друг друга и «алгоритмически / криптографически / надежно» отклоняющие неверные вычисления, что-то вроде «обмана» или «обмана» коррупция».
классический анализ параллелизма заключает, что существует около 7 «фундаментальных» типов шаблонов проблем, которые разлагаются на конкретные сбои параллельного выполнения. см. Исследование параллельных вычислений: взгляд из Беркли
Здесь есть некоторый элемент открытого теоретического вопроса, касающегося соображений производительности, рассмотренных в большинстве других ответов. Вопрос о том, существуют ли какие-либо проблемы, которые «по своей природе быстрее» параллельны, чем последовательные, также грубо известен как проблема P =? NC, где NC считается классом «эффективно распараллеливаемых» алгоритмов, а P - «эффективными [последовательными] алгоритмами». "
источник