Аппаратный ускоритель сортировки и поиска.

Сколько выслать денег?

PS: dk-, прости, я отнял у тебя комментарий.

Чип сортировки пузырьком.

Каюсь, думал, что автор Стиви. Перестал разбираться в сортах идиотов.

О, боже. Аппаратный ускоритель пузырьковой сортировки. Это эпик.

Неужели таких чипов ещё никто не делал?

Если хочешь быть в тренде, читай про cache-oblivious algorithms. А для затравки у Кнута про внешнюю сортировку можешь просмотреть.

Сколько выслать денег?

Пусть составит убедительный бизнес-план сперва :D

Лол, это и было в начале прошлого века.

Любишь подрочить на то, в чем вообще ничего не понимаешь?)

Как там тема про пневмопутепроводы по всей планете? Апнем?Г

Как там тема про пневмопутепроводы по всей планете?

Коварный Маск украл идею же. Проклятые копеталисты %)

Интересно, существуют ли аппаратные ускорители поиска и сортировки?

Давным-давно японцы на ПЛИС делали медианную фильтрацию видео в апертуре 5 х 5 сетью обменных модулей из 3 тома Кнута.

А сейчас на ПЛИС иногда делают сети сортировки те, кому нужно очень узкоспециализированное изделие для работы в жёстком реальном времени, например ранговая фильтрация локационных сигналов.

О, боже. Аппаратный ускоритель пузырьковой сортировки. Это эпик.

В 80-х годах прошлого века у японцев были машины для баз данных с дисковыми аппаратными сортировщиками (диск с 2 или 3 магнитными головками) методом пузырька. ©

Существуют базы с векторизацией, см. ClickStream

Как уже выше указали - это пузырьковая сортировка. Думаю, лучше бы какую более быструю.

И второе - кому оно надо? Всё равно с значительным объемом данных нам уже понадобится внешний накопитель с правильно организованными структурами данных (индексы там и прочие кеши).

Если в такой чип загрузить индекс базы данных

То это ускорит только работу с ним, а за данными всё равно лезь во внешнюю память. Не спец по БД и этому вашему хайлоду, но думаю - соотношение цены разработки такого решения и выигрыша из категории «нинужно».

то искать значения в нём можно будет буквально за 1 такт

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

з.ы. куда кидать деньги :-)

И да, конечно, там где большой объем не нужен, а время - важно - имеет право на жизнь (хотя, как уже писали - сам алгоритм сомнителен).

Как там тема про пневмопутепроводы по всей планете? Апнем?Г

Давно уже апнули, только на новом уровне, в виде юнибусов. Теперь изобретают рельсы-струны к которым можно подвешивать вагончики.

Светоча опять кинули?!

А Светоч у нас - Резидент?

12й!

Светоч у нас - Резидент?

Тебя в светочи без очереди зачислим, за многочисленные заслуги %)

Я, как главный инвестор, против!

Там тоже на пожертвованиях, что-то делают, но я совсем не уверен что акционеры сильно наварятся в случае успеха проекта. Всегда же можно в нужный момент первооткрывателей подвинуть:)

Ты правда йоба кулер пропустил?)

Это не светоч, это целый прожектор. Прожектор научной перестройки.

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

Цирк длинной полтора года!)

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

Ну пиши старт пост с реквизитами и целями)

Подозреваю, что это только книжка восьмидесятых годов, а сами железки гораздо старше. В 1983 они там NES выпускали по доступным ценам. Какой смысл в механических компьютерах в 1986-м?

алмазные теплопроводы

rezedent12, учись, как надо фонды выбивать! %)

то искать значения в нём можно будет буквально за 1 такт

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

Нет. Простейший «И» компаратор на каждой ячейке.

Не, я достаточное количество сложностей представляю. Писать должен человек, навроде Дениса, которому «а мне любое море, море по колено, а мне - любые горы по плечу».

алмазные теплопроводы

rezedent12, учись, как надо фонды выбивать! %)

Это никогда не было самоцелью.

Не понял идею. Может XOR? Но он сможет только определить равенство/неравенство, но не больше/меньше.

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

Получится сопроцессор типа видухи, со своей памятью и вентилятором.

И тут я понял, что туплю. Если нам нужно только извлечь данные по индексу - да, xor подойдет. Однако объем всё ещё навевает мне сомнения из разряда «а не проще ли держать в кеше помещающуюся в нём часть индекса».

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

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

Определенно надо ферму ASICов заказать тебе!

Впрочем, не суть - чтобы отсортировать массив за 1 такт - нам нужно одновременно сравнить значения всех ячеек.

Сравнивать за 1 такт все ячейки - это слишком жирно. Я предлагал делать 1 итерацию массива за 1 такт при сортировке методом «пузырька».

Подозреваю, что это только книжка восьмидесятых годов, а сами железки гораздо старше.

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

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

Ну вот и получается что за такт отсортировать - никак. Что до алгоритма - не вижу препятствий к тому, чтобы не приюзать хотя бы какой quicksort (ЕМНИП, будешь уже сортировать не C*N^2 тактов, а за C*N log(N)).

Что до извлечения записи по индексу - вот его по идее можно провести за 1 такт даже для немалых (относительно) объемов. Но если данных много - нам придётся или организовать память под них у себя (подозреваю, недешевое удовольствие - врядли на какую ПЛИС получится всунуть много памяти) или потребуется лезть в внешнюю память (да хоть какой-либо DDR) - но тогда будет ли фатален плюс перед системой из обычного процессора (или нескольких) с кешированным индексом?

Я ещё и читаю очень внимательно. Сортировка за такт - да, мой идиотизм.

Аппаратный замедлитель сгодится? Зато на халяву.

«сортировка на трех лентах»

Значение является хэшем значения который аппаратно считается при его помещении в ячейку.

коллизии и прочие боли же

Значение является хэшем значения который аппаратно считается при его помещении в ячейку.

коллизии и прочие боли же

Всё равно выборку которую сделает ускоритель по хэшам проверять потом. Цель то не получить сразу единственно верное значение, а сузить пространство поиска до нескольких элементов.

смотрел на трубе разборку авиационной всякой электроники,
да наверное и корабельно-подводная из того же репертуара.
в 60е++ годы,ИМХО, аж бегом делали специализированные механические вычислители.

Про ранний этап ничего не скажу, там вообще всё на реле Теслы и Ампера с Вольтом было :-)

Электроника парахеда 66го года постройки - во всю использовали логику на реле.

Ты лучше делай пометочку: имха, янизнаю, скажите как было.

мы, «достатошно молодое поколение», много чего не знаем о происходившем 100лет назад. А потом начинаются удивленные глазки - как так! 1930е годы, а кухни в Америке выглядят как наши сегодня? О_О миксер, пылесос, тостер О_О, блеять, блендер! Аааааа! кудах-кудах...

Вот смотришь хронику на трубе и охреневаешь.