Узкие» места, обусловленные иерархической структурой памяти

Предположим, что в компьютере решается какая-нибудь большая задача, например, система линейных алгебраических уравнений с матрицей максимального размера. Если используется метод Гаусса, то исключать эле­менты можно в самых различных порядках. При этом общее число выпол­няемых арифметических операций остается одним и тем же или меняется не более чем в 2—3 раза. Однако, выполняя разные варианты метода для од­ного и того же компьютера, можно увидеть, что общее время решения задачи меняется во много раз. Другая реальная ситуация. Пусть зафиксирован какой-либо вариант метода Гаусса, но теперь решаются системы различных размеров. При этом ожидается, что общее время решения задачи будет ме­няться пропорционально общему числу арифметических операций. Но и в этом случае встречаются неожиданности. Иногда для некоторых порядков время решения задачи может оказаться существенно большим.

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

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

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

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

Следующий уровень памяти – это кэш-память. Она тоже имеет свою иерархическую структуру, состоящую из 2-3 уровней. Кэш-память является своеобразным буфером между регистровой памятью и оперативной памятью. В современных компьютерах ее объем достигает многих миллионов байт. Управляет использованием кэш-памяти устройство управления.

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

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

Если для реализации алгоритма нужно не просто составить какую-нибудь программу, а добиться, чтобы она работала максимально быстро, то соблю­дение этих правил может дать ощутимый эффект. Как уже отмечалось, многие компьютеры особенно быстро осуществляют доступ к объектам с по­следовательными физическими адресами. Пусть, например, программа со­ставляется на языке Fortran. С точки зрения этого языка безразлично, про­водить обработку элементов массивов по строкам или столбцам. Безразлично это и с точки зрения сложности получаемой программы. Все различие сводится лишь к тому, что в одном случае имеют дело с преоб­разованием элементов каких-то матриц, а в другом — транспонированных к ним. Принимая во внимание специфику доступа к оперативной памяти, компиляторы с языка Fortran всегда располагают массивы в физической оперативной памяти последова­тельно по адресам, столбец за столбцом, слева направо и сверху вниз. Пред­положим, что реализуется алгоритм решения систем линейных алгебраиче­ских уравнений методом Гаусса. В этом случае время работы программы будет определяться ее трехмерными циклами. В зависимости от того, распо­ложена матрица системы в массиве по столбцам или строкам, внутренние циклы программы будут также осуществлять обработку элементов массивов по столбцам или строкам. Времена реализации обоих вариантов могут раз­личаться весьма заметно, иногда в несколько раз. Факт существенный, если речь идет о разработке оптимальныхпрограмм.

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

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

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

Контрольные вопросы

1. Зачем нужно оценивать производительность компьютеров?

2. Как оценивается пиковая производительность компьютера?

3. Почему реальная производительность отличается от пиковой производительности?

4. Какие срелства используются для оценки производительности компьютеров?

5. Как влияет структура подсистемы памяти на производительность компьютеров?