Какова противоположность “смущающе параллели”?
После каждого вызова strtol, ptr будет указывать на первый байт в строке, который не является частью проанализированного целого числа. Это будет вашей отправной точкой на следующей итерации. Поскольку fgets возвращает строку с новой строкой, цикл до ptr указывает либо на новую строку, либо на нулевой байт в конце строки.
char *ptr, *tmp;
tmp = chter;
do
{
li1 = strtol(tmp, &ptr, 2);
printf("%c", li1);
tmp = ptr;
} while ((*ptr != '\n') && (*ptr != '\0'));
17 ответов
по существу последовательный .
Пример: количество женщин не уменьшит продолжительность беременности.
Полностью без параллелизуемого? Возможно ли распараллеливание?
Конечно, вы могли бы, однако я думаю, что оба «имени» не являются проблемой. С точки зрения функционального программирования можно сказать, что «раздражающе последовательная» часть является наименьшей более или менее независимой частью алгоритма.
Хотя «смущающая параллель», если не принимать параллельный подход, является плохой практикой кодирования.
Таким образом, я не вижу смысла давать этим вещам имя, если хорошая практика кодирования всегда состоит в том, чтобы разбить ваше решение на независимые части, даже если вы в этот момент не пользуетесь параллелизмом.
«Совершенно серийно?»
Вас не должно удивлять, что ученые больше думают о том, что можно сделать, чем о том, что нельзя сделать. Особенно в этом случае, когда альтернативой распараллеливанию является все, как обычно.
Противоположностью смущающей параллели является Закон Амдала , который гласит, что некоторые задачи не могут быть параллельными, и что минимальное время, которое потребуется для совершенно параллельной задачи, продиктовано чисто последовательная часть этой задачи.
Все это связано с зависимостями данных. Смущающие параллельные проблемы - это проблемы, решение которых состоит из множества независимых частей. Проблемы с противоположностью этой природы будут те, которые имеют огромные зависимости данных, где практически ничего не может быть сделано параллельно. Дегенеративно зависимый ?
Мне трудно не публиковать это ... потому что я знаю, что это ничего не добавляет к обсуждению ... но для всех поклонников южного парка там
"Супер сериал! "
Чаще всего я слышал термин «тесно связанный», так как каждый процесс должен часто взаимодействовать и взаимодействовать, чтобы обмениваться промежуточными данными. По сути, каждый процесс зависит от других, чтобы завершить свои вычисления.
Например, матричная обработка часто включает совместное использование граничных значений на краях каждого раздела массива.
Это контрастирует с досадно параллельными (или слабосвязанными) проблемами, где каждая часть проблемы полностью автономна, и IPC не требуется (или очень мало). Подумайте о параллелизме мастера / рабочего
Я всегда предпочитал «к сожалению, последовательный», как этап разделения при быстрой сортировке.
«стандартные примеры» последовательных процессов:
- рождение ребенка: «Программы сбоя терпят неудачу, потому что они основаны на теории, согласно которой, если девять беременных женщин, вы можете родить ребенка в месяц. ” - приписывается Вернеру фон Брауну
- вычислению числа пи, е, sqrt (2) и других иррациональных чисел до миллионов цифр: большинство алгоритмов последовательной
- навигации: чтобы добраться из точки A в точку Z, вы должны сначала перейти через некоторые промежуточные точки B, C, D и т. д.
- Метод Ньютона: вам нужно каждое приближение, чтобы вычислить следующее, лучшее приближение
- аутентификация запрос-ответ
- усиление ключа
- хэш-цепочка
- Hashcash
Существует более чем одна противоположность «до неприличия параллельная» проблема.
Совершенно последовательная
Противоположной является проблема непараллелизации , то есть проблема, для которой невозможно ускорение за счет использования более одного процессора.Уже было опубликовано несколько предложений, но я бы предложил еще одно название: идеально последовательная проблема.
Примеры: задачи, связанные с вводом-выводом , тип задач «вычислить f 1000000 (x 0 )», вычисление определенного криптографического хэша функции .
Интенсивное общение
Другой противоположностью является проблема с параллелизацией, которая требует большого количества параллельного обмена данными (проблема , требующая интенсивного обмена данными ). Реализация такой проблемы будет правильно масштабироваться только на суперкомпьютере с межсоединением с высокой пропускной способностью и малой задержкой. Сравните это с досадно параллельными проблемами, реализации которых эффективно работают даже в системах с очень плохим межсоединением (например, фермы ).
Яркий пример проблемы с интенсивным обменом данными: решение A x = b , где A - большая плотная матрица. Собственно реализация задачи используется для составления рейтинга TOP500 . Это хороший тест, поскольку он подчеркивает как вычислительную мощность отдельных процессоров , так и качество межсоединений (из-за интенсивности связи).
В более практическом плане любая математическая модель, которая решает систему дифференциальных уравнений в частных производных на регулярной сетке с дискретным шагом времени (подумайте: прогнозирование погоды, in silico краш-тесты), может быть распараллелена с помощью ] декомпозиция области .Это означает, что каждый ЦП заботится о части сетки, и в конце каждого временного шага ЦП обмениваются своими результатами на границах области с «соседними» ЦП. Эти обмены делают этот класс проблем трудоемким.
Пример последовательной проблемы. Это распространено в пакетах САПР и некоторых видах инженерного анализа.
Обход дерева с зависимостями данных между узлами.
Представьте себе обход графа и суммирование весов узлов.
Вы просто не можете распараллелить это.
Программное обеспечение САПР представляет детали в виде дерева, и для рендеринга в объект необходимо пройти по дереву. По этой причине рабочие станции САПР используют меньше ядер и работают быстрее, чем много ядер.
Спасибо за внимание.