Почему компьютеры не поставляются со специализированным оборудованием, таким как сети сортировки?

10

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

MaiaVictor
источник
2
Купите плату PCI FPGA и реализуйте любые расширения, которые вам нравятся.
SK-logic
Оборудование не волшебство. Многие вещи не могут быть значительно ускорены (или вовсе) специальным оборудованием, и даже если это возможно, существующее оборудование часто необходимо адаптировать (или, по крайней мере, перекомпилировать). См. Yosefk.com/blog/its-done-in-hardware-so-its-cheap.html
3
@WorldEngineer Я не вижу, как это входит в картину. Ваш обычный пользователь не знает, для чего 80% вещей в современном процессоре, он счастлив, потому что им говорят, что это делает их программы быстрее (и это имеет ядро ​​правды). Если сортировка действительно так распространена, как предполагает OP, и ее можно оптимизировать с помощью выделенного оборудования, они поместили бы ее рядом с предиктором ветвления («что это, садоводство?»), Выпустили пресс-релиз, в котором говорилось, что они сделали приложения X и Y 5%. быстрее и продай.
1
Это напоминает мне идею консервационных ядер , которые нацелены на энергоэффективность, а не на пиковую производительность.
Пол А. Клейтон,

Ответы:

19

Прежде всего, компьютеры поставляются со специализированным оборудованием . Каждый ноутбук и настольный компьютер, продаваемый в течение нескольких лет, теперь имеет специализированный сопроцессор, графический процессор, который обрабатывает алгоритмы обработки изображений, такие как приложения для видео и игр. Очень большие компьютеры ( например , «суперкомпьютеры», семейство IBM System Z) имеют множество специализированных процессоров для обработки числовой обработки («векторной обработки») и т . Д.

Во-вторых, сортировка является одним из наиболее изученных аспектов вычислительной техники и оказывается слишком сложной, чтобы ее можно было встроить в аппаратное обеспечение для более простых случаев. Сортировка это все о скорости и правильности. Скорость зависит от выбора алгоритма, типа и вариации данных и объема данных. Правильность зависит от типа и контекста данных. Положительно тривиально сортировать массив целых чисел среднего размера, который вписывается в собственный размер слова ЦП ( например,, 31 или 63 бита плюс знак). Сортировка строк символов, которые содержат больше, чем просто значения ASCII, чрезвычайно сложна - 20 лет назад IBM опубликовала книгу из 500 с лишним страниц, просто обсуждая проблемы наборов символов в контексте национальных границ и общего использования. И затем возникает вопрос о несмежных данных - сортировка связанного списка включает погоню указателей по всей памяти.

Росс Паттерсон
источник
10

Основная проблема заключается в том, что алгоритмы сортировки (1) нуждаются в большой гибкости, и (2) было бы очень сложно ускорить использование аппаратного обеспечения в любом случае.

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

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

В отличие от этого, мультимедийные приложения (аудио и графика, особенно 3D-графика) используют некоторые очень повторяющиеся структуры - конечно, есть гибкость, но она построена на основе большого и очень хорошо структурированного фундамента. Это позволило графическому ускорению начать с простых вещей, таких как Blitting (настраиваемая, но все еще очень структурированная операция копирования блоков) и рисование линий / полигонов. Это означало, что по мере усложнения обработки графики и звука векторные операции стали очевидной целью оптимизации - сначала MMX (векторы целых чисел), а затем SSE (векторы чисел с плавающей точкой). Это означало, что была довольно четко определенная структура для работы механизма трехмерной графики, когда старый конвейер трехмерной графики с фиксированной функцией был перенесен на аппаратное обеспечение трехмерной графики.

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

Графические процессоры в настоящее время являются духовными или фактическими потомками цифровых сигнальных процессоров, которые были (и, вероятно, все еще) являются своего рода специализированным процессором для обработки цифровых сигналов (например, аудио).

Что приводит к конечной точке - алгоритмы сортировки могут быть ускорены аппаратно. В зависимости от ваших данных, сортировка может выполняться с использованием инструкций MMX или SSE (одна инструкция-несколько данных) на вашем процессоре, но, вероятно, нет особого смысла из-за проблемы с пропускной способностью памяти - возможно, вы можете быть немного более энергоэффективными таким образом, хотя. Тем не менее, вы также можете использовать графическое оборудование. Таким образом, вы можете получить выгоду от часто гораздо лучшей пропускной способности памяти для видеокарт. Вы не сможете заменить все виды таким образом, но это, безусловно, возможно и, вероятно, делается там, где это необходимо.

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

Steve314
источник
3

Но они делают! Они называются расширениями набора команд. (Вещи, как SSE и тому подобное)

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

Если вы посмотрите на аппаратное обеспечение, которое могло бы сделать это, я думаю, вы бы смотрели на что-то вроде FPGA. Как вы можете видеть с FPGA, чип станет намного дороже, хотя он не будет применим для многих приложений.

О нет
источник
Мне придется гуглить по SSE, но заранее сортировка наверное универсальная. Это реализовано на аппаратном уровне?
MaiaVictor
А также, как мы там, вы бы порекомендовали книги?
MaiaVictor
Я только что говорил об оптимизации работы, которая была реализована на процессорах в стиле CPU в целом, поскольку в качестве примера используются сети сортировки. Я не знаю, включает ли SSE или любой другой набор инструкций сортировку определенных оптимизаций. Я занимался сортировкой сетей Google, и, поскольку существуют оптимизированные общие реализации, я думаю, что программные реализации могли бы выполнять свою работу так же хорошо, если реализация сделана правильно.
Онно
Я должен отметить, что большинство расширений набора команд работают на более низком уровне, чем сеть сортировки, которую вы использовали в качестве примера, но не исключено, что можно разработать оптимизацию с несколькими регистрами, которая может выполнить сортировку таким образом. Но вопрос для производителей процессоров будет: «Окупится ли оно достаточно, чтобы оправдать затраты?».
Онно