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

[B@R5uk]

Читаю тут Парлетт Б. (Parlett) - Симметричная проблема собственных значений. Численные методы (1983, Мир). Она довольно старенькая, и мне попался такой абзац:

Цитата:

С развитием машинной технологии время, необходимое для выполнения одного умножения, сократилось (с ${}_{{}_.}10^{-3}$ с в 1955 г. до ${}_{{}_.}10^{-6}$ с в 1970), вследствие чего продолжительность малых матричных вычислений по-видимому упала ниже той черты, за которой она заслуживает внимания. Хотя так обстоит дело на больших ЭВМ, картина может значительно измениться по мере того, как всё больше малых вычислений выполняются на мини-процессорах, настольных машинах и даже на ручных калькуляторах. Возможно, наступит день, когда выборка данных из памяти потребует большего времени, чем умножение.

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

[мат-ламер]

B@R5uk в сообщении #1685767 писал(а):

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

Да. Вы понимаете всё правильно. С памятью реально есть проблемы. Вот статья .

[Dmitriy40]

B@R5uk в сообщении #1685767 писал(а):

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

Смотря что понимать под "подгрузкой данных" - если время до получения первого элемента по случайному адресу, то да, если же скорость потока последовательных элементов (как в названии темы), то нет. Так что вопрос терминологии: скорость обращения (время доступа) как была низкой (50нс), так и осталась (12нс), а вот скорость передачи данных выросла очень значительно (с 50Мбит/с на контакт для EDO DRAM до 32Гбит/с на контакт для GDDR7).
И кроме кэшей применяют и другие методы борьбы с низкой отзывчивостью (большим временем доступа) памяти, например в GPU запускают одновременно сотни потоков на одном аппаратном АЛУ - пока каждый поток ждёт данных из памяти выполняются другие потоки, дождавшиеся своих данных. Если потоков больше задержки доступа - простоев не будет. Этакий гипер-гипер-гипер-трейдинг.

[zgemm]

B@R5uk в сообщении #1685767 писал(а):

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

этот день наступил когда появился Cray-1, и это было раньше, чем Парлет написал свою книженцию. Если не говорить о таких странных высказываниях, в остальном - книжка довольно разумная, я этой книжкой 30 лет назад зачитывался. Кстати, на нескольких докладах и последующих кулуарных обсуждениях в начале 2000ых Парлет выглядел частенько тормозом, по крайней мере на фоне Демеля и Годунова, так что не судите, пожалуйста, Парлета строго.

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

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

Но, по видимому, Парлету было вподляк Годунова (по задачам на собственные значения) и Воеводина (по этому вопросу) цитировать, вот и вылезло такое странное утверждение.

[mihaild]

zgemm в сообщении #1694912 писал(а):

трафик - это перенос данных с одного физического места на другое и расстояние с годами почти не уменьшается

Расстояние накладывает ограничение на latency ($\text{расстояние} / c$), но не накладывает ограничения на throughtput. Грузовики с дисками можно отправлять колоннами.

[zgemm]

mihaild в сообщении #1694918 писал(а):

Грузовики с дисками можно отправлять колоннами.

так нет же!!! Грузовик-то длинный получается, с половину длины волны, а затворы в FETах быстрее 10ГГц щелкать не могут, вот и грузовик получается с сантиметр длинной. Вы конечно же сразу возразите, де давай много дорожек и по каждой свой грузовик. Да, так делают, но дорожки начинают друг другу мешать, их надо экранировать, и уже 20-30 serdes впараллель очень тяжело провести, особенно если их надо с точностью до миллиметра выравнивать.

[mihaild]

zgemm в сообщении #1694919 писал(а):

а затворы в FETах быстрее 10ГГц щелкать не могут

Это дает ограничение на throughput, но я не вижу, как в него входит длина дорожки.

[zgemm]

mihaild в сообщении #1694921 писал(а):

zgemm в сообщении #1694919 писал(а):

а затворы в FETах быстрее 10ГГц щелкать не могут

Это дает ограничение на throughput, но я не вижу, как в него входит длина дорожки.

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

[mihaild]

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

Хорошо, у нас есть физическое ограничение на длину волны, оно же ограничение на частоту. Я вижу, как из него получается ограничение на пропускную способность (ограничение на частоту это примерно и есть ограничение на пропускную способность в битах). Я не вижу, где в этом ограничении участвует длина шины. Т.е. каким образом получается, что по шине длиной 10см и 1км можно за секунду передать разное количество бит.

[B@R5uk]

mihaild в сообщении #1694925 писал(а):

Т.е. каким образом получается, что по шине длиной 10см и 1км можно за секунду передать разное количество бит.

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

В масштабах материнской платы помехи, наверное, тоже будут появляться. Интересно было бы почитать что-нибудь ознакомительное про эту всю схемотехнику, в объяснении кого-нибудь компетентного. Я часто видел, как на материнках дорожки идут зигзагом, чтобы выровнять их длину между собой при параллельной передаче. Интересно, если каждую дорожку использовать асинхронно (то есть не зависимо друг от друга), не будет ли это более эффективным методом передачи данных? Типа как USB или USART или SATA, только в масштабах платы между быстродействующими устройствами на ней. За это придётся платить усложнением внутренности чипов, за то не надо будет так сильно мучиться с разводкой: требования на синхронность прихода данных отпадут, требования к шумовым наводкам тоже снизятся (плюс контроль ошибок передачи, который и в текущих версиях должен быть). Современные видеокатры, если я не ошибаюсь, как таким интерфейсом к системе и подключаются. Во всяком случае слот, в который они втыкаются (PCIe ?), значительно меньше, чем он когда-то был (AGP и прочие).

[Dmitriy40]

B@R5uk в сообщении #1695013 писал(а):

Интересно, если каждую дорожку использовать асинхронно (то есть не зависимо друг от друга), не будет ли это более эффективным методом передачи данных?

При наличии технической возможности (раздербанить поток данных на независимые/асинхронные потоки и потом корректно собрать обратно, это проблема, плюс заметно повышается латентность) - да, будет. PCIe так и устроена, плюс там автоматический выбор сколько линий физически соединены (потому видеокарта x16 вполне работает в слотах и x8, и x4, и x1, если её туда физически засунуть).

[bondkim137]

mihaild в сообщении #1694921 писал(а):

Это дает ограничение на throughput, но я не вижу, как в него входит длина дорожки.

Достоверность бита экспоненциально падает с ростом длины маршрута.

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

При использовании протоколов с переотправлением потерянных данных (вроде сетевых протоколов, таких как TCP) пропускная способность канала по очевидным причинам напрямую зависит от latency. На практике - качать в Москве что-то с сервера в Австралии при прочих равных заметно медленнее, чем с локального. Более коротких маршрутов это тоже касается, например в USB тоже есть retransmission и длина кабеля на практике часто влияет на пропускную способность. И в PCI-E тоже есть retransmission - там падение пропускной способности в обычных условиях не так заметно, но при использовании проводных райзеров тоже иногда всплывает. В многопроцессорных системах тоже используются протоколы с retransmission в каналах между физическими процессорами (например, IntelQPI). Как и в протоколах, соединяющих видеокарты (например, NVLink, который заменил SLI).

[realeugene]

bondkim137 в сообщении #1702164 писал(а):

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

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

-- 03.10.2025, 10:40 --

bondkim137 в сообщении #1702164 писал(а):

И в PCI-E тоже есть retransmission - там падение пропускной способности в обычных условиях не так заметно, но при использовании проводных райзеров тоже иногда всплывает. В многопроцессорных системах тоже используются протоколы с retransmission в каналах между физическими процессорами (например, IntelQPI). Как и в протоколах, соединяющих видеокарты (например, NVLink, который заменил SLI).

А вот в грузовике, набитом флешками, с ошибками борются при помощи FEC, и из бэкапов восстанавливать приходится крайне редко, при общей ненадёжности флешей.

-- 03.10.2025, 10:58 --

B@R5uk в сообщении #1695013 писал(а):

Я часто видел, как на материнках дорожки идут зигзагом, чтобы выровнять их длину между собой при параллельной передаче. Интересно, если каждую дорожку использовать асинхронно (то есть не зависимо друг от друга), не будет ли это более эффективным методом передачи данных?

До некоторой степени так и делают - в DDR памяти есть сложная процедура инициализации с тестированием линий и выбором оптимальных параметров приёма. Всё это компромисс между сложностью PCB и сложностью реализации приёмопередатчиков в чипах. Причём, за счёт усложнения чипов и протоколов прогресс скорости передачи данных через соединения на плате всё ещё экспоненциальный. При этом задержка на чтение, требующая двунаправленной передачи пакетов или подготовки чтения новой стоки ячеек в матрице памяти, почти не уменьшается. Но однонаправленная пропускная способность всё растёт и растёт.

[realeugene]

bondkim137 в сообщении #1702164 писал(а):

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

Возьмём дискретный AWGN канал. Пусть на длине $L$ сигнал/шум падает в нём на $E$ dB. Поставим в середине усилитель, восстанавливающий первоначальную мощность сигнала. Сигнал/шум на этой же длине станет падать на $E/2 + 3$ dB. Ставя промежуточные усилители и восстановители сигнала можно уменьшать помехи на больших длинах, ещё до кодирования. Что и используется в межконтинентальных кабелях.

[bondkim137]

realeugene. Грузовики тоже достаточно часто попадают в аварии, где FEC не сильно поможет, и нужна будет ретрансмиссия всего грузовика и/или реализация FEC на уровне нескольких грузовиков. Ничего не могу сказать о практике реализации подобных гипотетических операторов связи, но вот в межконтинентальных кабелях и сопутствующей проводной инфраструктуре пакеты прекрасно теряются уже после всех FEC, и с этими потерями приходится работать в контексте ретрансмиссии как высокоуровневым сетевым протоколам обмена данных, таким как TCP и различным вариациям RUDP, так и ниже, например в Fibre Channel.