Алгоритмы побеждают закон Мура


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

Возможно, это не новость, но это противоречиво.

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

Идея в том, что алгоритмы побеждают закон Мура. Идея была опубликована в академическом блоге Algorithmic Game-Theory / Economics, в котором обсуждались некоторые интересные утверждения в отчете о научной политике «Доклад президенту и Конгрессу: проектирование цифрового будущего: НИОКР в области сетевых технологий и ИТ, финансируемые из федерального бюджета».

Пока нечего волновать, и на самом деле все это выглядит действительно скучно, но … Утверждается, что, хотя закон Мура, заключающийся в том, что количество транзисторов на микросхеме будет удваиваться каждые 1-2 года, не имеет значения как закон вычислений. улучшение по сравнению с тем, что было достигнуто в программном обеспечении. Приводится аргумент, что за 15-летний период закон Мура дал увеличение в 1000 раз, но улучшения в алгоритмах дали более чем 43000-кратное увеличение.

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

Аппаратные улучшения происходят достаточно стабильно и время от времени останавливаются из-за того, что сталкиваются с той или иной технологической стеной. Например, в настоящее время нам трудно выйти за пределы тактовой частоты 3Ghz. Но всякий раз, когда разработка оборудования наталкивается на такую стену, она просто поворачивает в новом направлении. Следовательно, вы не можете построить более быстрый процессор, но вы можете построить больше процессоров, и поэтому улучшения в оборудовании поворачивают за угол и направляются к многоядерности.

Теперь сравните это с улучшением алгоритма. В большинстве случаев нет очевидного способа улучшить алгоритм. Если бы это было так, мы бы в первую очередь использовали лучший алгоритм. Так что алгоритмические улучшения сложны и нуждаются в «прорывном» моменте. Вы можете оглянуться на историю алгоритмов, чтобы перечислить несколько хорошо известных таких достижений. Например, быстрое преобразование Фурье БПФ сделало возможной большую часть обработки сигналов в реальном времени.

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

А теперь угадайте, какой 15-летний период и какой предмет используются в рекомендациях по политике для своих данных?

Да, у вас это есть. Это период с 1988 по 2003 год, и предметом является линейное программирование, когда в этот период были введены новые революционные алгоритмы.

Итак, если мы подождем еще 15 лет, будет ли линейное программирование в 43000 раз эффективнее?

Наверное, нет, если только оборудование не намного быстрее.

Нужны ли нам лучшие алгоритмы?

Конечно.

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

Почти наверняка нет.

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


Добавить комментарий