4)Сбалансированные и несбалансированные деревья поиска.

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

Если дерево поиска близко к сбалансированному, то даже в худшем случае за время порядка O(log2n) в нем можно:

• Найти вершину с заданным значением или выяснить, что такой вершины нет.

• Включить новую вершину.

• Исключить вершину.

Среднее время выполнения этих операций будет также близким к O(log2n), так как в идеально сбалансированном дереве при полностью заполненных уровнях на последнем уровне находится больше половины узлов дерева.

Например, последовательность значений 4, 6, 2, 1, 5, 3, 7 дает следующее идеально сбалансированное дерево:

В этом дереве 7 узлов, на последнем уровне находится 4 узла.

Если доступ к одному узлу требует 1 единицу времени, то до узла 4 можно добраться за 1 единицу времени, до 2 и 6 - за 2, до 1, 3, 5, 7 - за 3.

То есть в худшем случае требуется 3 единицы времени, в среднем: (1+2*2+3*4)/7 = 2.4 единицы времени.

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

Например, последовательность значений 1, 7, 2, 6, 3, 5, 4 дает следующее вырожденное дерево:

Р абота с таким вырожденным деревом потребует в худшем случае 7 единиц времени (доступ к 4), а в среднем: (1+2+3+4+5+6+7)/7 = 4 единицы времени.

То есть для вырожденного дерева затраты на доступ к узлам в худшем случае имеют порядок O(n), в среднем - O(n/2). Разница во времени доступа будет гораздо заметнее при большем числе узлов.

Напр, в идеально сбалансированном дереве из 1023 узлов время доступа в худшем случае будет равно 10 единицам времени, в среднем:

единицам времени.

А в вырожденном дереве из 1023 узлов потребуется в худшем случае 1023 единицы времени, в среднем - 512 единиц времени.

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

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

Билет №18.

1)Иерархия запоминающих устройств. Кэш-память. Способы отображения основной памяти на кэш. Схемы выполнения запросов в системах с кэш-памятью.

Иерархия запоминающих устройств. Память вычислительной машины представляет собой иерархию запоминающих устройств (ЗУ), отличающихся средним временем доступа к данным, объемом и стоимостью хранения одного бита. Фундаментом этой пирамиды запоминающих устройств служит внешняя память, как правило, представляемая жестким диском. Она имеет большой объем, но скорость доступа к данным является невысокой.

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

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

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

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

Неотъемлемым свойством кэш-памяти является ее прозрачность для программ и пользователей. Система не требует никакой внешней информации об интенсивности использования данных; ни пользователи, ни программы не принимают никакого участия в перемещении данных из ЗУ одного типа в ЗУ другого типа, все это делается автоматически системными средствами.

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

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

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

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

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

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

В действительности запись в кэше обычно содержит несколько элементов данных.

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

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

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

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

Схемы выполнения запросов в системах с кэш-памятью

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

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

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

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

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