Почему последовательный поиск в компьютерных системах менее эффективен параллельного?

Последовательный поиск в компьютерных системах может быть менее эффективен параллельного по нескольким причинам:

• Затраты на обмен данными между процессорами. 1 Передача информации — медленная операция, и время на неё может «съесть» весь выигрыш, полученный за счёт распараллеливания вычислений. 3
• Сложность адаптации последовательных алгоритмов к параллельным системам. 1 Значительная доля хорошо зарекомендовавших себя алгоритмов не имеет эффективных параллельных аналогов. 1
• Неопределённость в порядке выполнения действий. 1 Одна и та же программа на одних и тех же данных может давать верные результаты, но при очередном запуске с теми же данными выдавать непредсказуемый результат. 1
• Проблема «гонки данных». 3 Процессоры, работающие параллельно, могут получать доступ к одним и тем же данным, хранимым в общей памяти, как для чтения, так и для записи. 3

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