Какая модель вычислений является «лучшей»?

41

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

В результате мы имеем дюжину алгоритмов для, например, SORT-задачи для разных моделей вычислений. К сожалению, мы даже не можем быть уверены, что реализация алгоритма со временем выполнения O (n) в слове RAM с разрешенными битовыми векторами операциями будет выполняться быстрее, чем реализация алгоритма со временем выполнения O (n⋅logn) в слово RAM (я говорю только о «хороших» реализациях, конечно).

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

Татьяна Стариковская
источник
1
Перекрестная публикация на MathOverflow ( mathoverflow.net/questions/44558/… ), хотя и перенаправлена ​​сюда.
Дэйв Кларк
@ Татьяна, Хороший вопрос, что вы подразумеваете под "лучшим"? Вы имеете в виду модель с теоретическим временем выполнения, близким к «реальному» времени выполнения?
Мухаммед Аль-Туркистани
8
Если вы хотите точно смоделировать «реальное» время работы, то, возможно, важно точно смоделировать кеши. В частности, современные вычисления имеют много уровней кэширования (CPU, RAM, Disk и т. Д.), Причем некоторые уровни на несколько порядков медленнее, чем другие; не исключено, что «реальное» время выполнения алгоритма будет определяться количеством пропущенных кешей. Как ни странно, я слышал, что одна из причин, по которой барьерные методы в линейном программировании работают так хорошо, несмотря на свои слабые теоретические гарантии, заключается в том, что они часто весьма эффективно кешируют.
Мм
4
Насколько я могу судить, как говорит mhum, самые большие расхождения в прогнозируемом времени выполнения в словесной модели RAM и реальном времени выполнения обычно возникают из-за извлечения данных ... неправильные переменные находятся в кешируемой памяти, а время поиска замедляется очень сильно из-за этого. Было предпринято несколько попыток смоделировать это с помощью теоретической модели иерархической памяти, и я не верю, что какая-либо из этих попыток была очень успешной, потому что модели оказываются слишком сложными, чтобы с ними легко работать.
Питер Шор
2
Если у вас есть алгоритм, который, по вашему мнению, может быть полезен на практике, и вы хотите, чтобы он действительно использовался, лучшее, что вы можете сделать, чтобы убедиться в этом, - это внедрить его или заставить кого-то другого реализовать его (даже если это не очень хорошо). достаточно реализации для включения в практическое программное обеспечение). Для примера в этом, посмотрите на историю алгоритма сжатия данных LZW. На самом деле, вероятно, нет смысла пытаться понять, как кеширование влияет на алгоритм, если только он не заинтересован в реализации; иначе никто не обратит внимания на ваши результаты.
Питер Шор

Ответы:

30

Я всегда считал стандартную модель Word RAM «лучшей» в вашем смысле. Каждый, кто научился программировать на языке, подобном C (или любым свободным эквивалентам, таким как Java и т. Д.), Имеет в виду именно эту модель, когда думает о компьютере.

Конечно, иногда вам нужны обобщения в зависимости от режимов, в которых вы работаете. Модель внешней памяти является важной, чтобы иметь в виду. Это относится не только к работе с дисками, но и к пониманию (заставляет вас заботиться) о кеше. Конечно, слишком серьезное отношение к нему может также привести к бессмысленным результатам, поскольку модель чистой внешней памяти не учитывает вычисления. Еще одно обобщение Word RAM - это параллелизм, но сейчас мы все немного запутались :)

О(N)О(NЛ.Г.N)NN

Последнее замечание об алгоритмах и «реальности»: всегда имейте в виду, чего вы пытаетесь достичь. Когда мы работаем в алгоритмах, мы пытаемся решить самые сложные проблемы (например, SAT на 50 переменных или сортировка миллиардов чисел). Если вы пытаетесь отсортировать 200 чисел или решить SAT по 20 переменным, вам не нужен какой-либо сложный алгоритм. Вот почему большинство алгоритмов на самом деле являются тривиальными. Это не говорит ничего плохого об алгоритмических исследованиях - нас просто интересует та необычная 1/1000 реальных проблем, которые оказываются сложными ...

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

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

Многоленточная машина Тьюринга, безусловно, теоретически хорошо определена, и многие алгоритмы были разработаны и проанализированы в этой модели на протяжении многих лет. Однако для некоторых это недостаточно тесно связано с тем, как работают настоящие компьютеры, чтобы быть действительно хорошей моделью для использования в 21 веке. С другой стороны, модель word-RAM стала популярной и, похоже, более точно отражает работу современных компьютеров (операции со словами, а не битами, постоянный доступ к ячейкам памяти). Однако есть аспекты, которые не идеальны. Например, нет модели с одним словом RAM. Сначала нужно указать, какие операции со словами должны быть разрешены в постоянное время. Есть много вариантов для этого без единого принятого ответа. Во-вторых, размер слова w обычно устанавливается с ростом входного размера (который, по крайней мере, так же быстр, как log (n)), чтобы можно было адресовать любой элемент в памяти, используя постоянное количество слов. Это означает, что нужно представить себе бесконечный класс машин, на которых работает ваш алгоритм или, что еще хуже, что машина меняется по мере того, как вы передаете ей больше данных. По крайней мере, эта мысль сбивает с толку самых чистых среди моих учеников. Наконец, вы получаете несколько неожиданные результаты сложности с моделью «слово-память», которая может не совпадать с теми, которые изучаются студентом. Например, умножение двух n-битных чисел в этой модели на O (n) время, а простое чтение в n-битной строке является внезапно сублинейной временной операцией. Это означает, что нужно представить себе бесконечный класс машин, на которых работает ваш алгоритм или, что еще хуже, что машина меняется по мере того, как вы передаете ей больше данных. По крайней мере, эта мысль сбивает с толку самых чистых среди моих учеников. Наконец, вы получаете несколько неожиданные результаты сложности с моделью «слово-память», которая может не совпадать с теми, которые изучаются студентом. Например, умножение двух n-битных чисел в этой модели на O (n) время, а простое чтение в n-битной строке является внезапно сублинейной временной операцией. Это означает, что нужно представить себе бесконечный класс машин, на которых работает ваш алгоритм или, что еще хуже, что машина меняется по мере того, как вы передаете ей больше данных. По крайней мере, эта мысль сбивает с толку самых чистых среди моих учеников. Наконец, вы получаете несколько неожиданные результаты сложности с моделью «слово-память», которая может не совпадать с теми, которые изучаются студентом. Например, умножение двух n-битных чисел в этой модели на O (n) время, а простое чтение в n-битной строке является внезапно сублинейной временной операцией.

Сказав все это, если вы просто хотите знать, будет ли ваш алгоритм работать быстро, то, скорее всего, это будет делать :-)

Рафаэль
источник
2
Я думаю, что если вы отказываетесь от побитовых или словесных арифметических операций, пытаясь избежать проблемы «машина растет с размером ввода», но все еще используете ОЗУ с одинаковыми затратами или машину указателя, то вы просто обманывают себя: эти другие модели имеют ту же проблему. Как они индексируют свой вклад? Ответ таков: на реальных компьютерах не хватает памяти, но, несмотря на это, все же удобнее разрабатывать алгоритмы для них, предполагая, что они являются ОЗУ (или, может быть, даже лучше использовать модель, учитывающую затраты на иерархию памяти), чем предполагая, что они ДФА.
Дэвид Эппштейн
4
Например, модель оперативной памяти, которую обсуждает Кнут, стоит w времени, чтобы найти адрес с w битами, и аналогично w времени, чтобы добавить два w битных числа (именно так он получает Theta (n log n) за время, умноженное на два n -битные числа в модели ОЗУ без каких-либо операций с постоянным временем над словами). Интересно, как наиболее широко принятые модели изменились за последние 20 лет и сколько моделей вообще больше никогда не обсуждается.
Рафаэль
8

Модели просто модели. Я бы не стал слишком далеко продвигаться; они говорят что-то о некоторых аспектах ваших алгоритмов, но не всю правду.

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

(На самом деле, просто реализация вашего алгоритма без его запуска уже говорит вам об этом ... Во-первых, он реализуемо доказуемо.)

Юкка Суомела
источник
3
Ну, у меня есть два возражения. Во-первых, не так много теоретиков реализуют алгоритмы, и все же мы должны как-то их сравнивать. Во-вторых, я хочу понять, какие возможности компьютера мы можем добавить в модель, не теряя при этом своей простоты.
Татьяна Стариковская
11
Решение, предложенное Дэвидом Джонсоном для этого, состоит в том, чтобы большее количество людей реализовывало алгоритмы - он начал ALENEX и DIMACS Challenges, чтобы решить эту проблему. У меня также есть некоторый опыт с этим. С Кеном Кларксоном я разработал рандомизированный алгоритм выпуклой оболочки, который, по нашему мнению, будет хорошо работать на практике. Кларксон велел студенту в Bell Labs заниматься этим. Исходя из обещания этой реализации, идеи были включены в программу qhull (написанную в Центре геометрии), но с некоторыми эвристическими ускорениями, что означает, что алгоритм больше не имеет теоретической гарантии того, что он работает быстро.
Питер Шор
5

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

Для современных многоядерных компьютеров параллельный вариант, представленный Arge, Goodrich, Nelson и Sitchinava в 2008 году, может быть точной моделью.

Рико Джейкоб
источник
5

Если вы имеете в виду «лучшую» вычислительную модель, которая сделает вашу жизнь более сложной, то вы можете использовать универсальную машину Тьюринга с 2 состояниями и 3 символами Wolfram.

ПРОФИ : нет, кроме ощущения ходьбы по тонкой грани между разумом и сумасшествием;

Минусы : тонн ...

:-D (только шутка, я в принципе согласен с предыдущими ответами ...)

Марцио де Биаси
источник
1

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

Цитировать из резюме:

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

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

user76284
источник