Подсистемы хранения данных
Решение на бумаге
Сама по себе теория протекания довольно-таки молода по меркам современной науки. Основные ее идеи были сформулированы в 1957 году при изучении явления прохождения газов через угольный фильтр, но со временем выяснилось, что новая теория способна описать широчайший круг явлений из таких областей, как физика и химия. Поэтому в настоящем теория перколяции получила весьма широкое распространение. Например, в контексте исследуемой нами темы эта теория позволяет определить характер состояния системы из большого числа связей, при условии, что они носят случайный характер, то есть могут быть заданы при помощи генератора случайных чисел.
Для того чтобы яснее представить обоснование предложенной учеными IBM схемы, обратимся к решению трех классических задач теории протекания. Две из них были приведены и практически доказаны в 1974 году американцами Б. Уотсоном (B. Watson) и П. Лизом (P. Leath).
Первый эксперимент американских ученых производился с экранной сеткой, состоящей из 137х137 узлов с расстоянием 6,35 мм, которые были припаяны к источнику постоянного тока и омметру. Путем поочередного разрезания контакта в узлах (рис. 1) решетки, инициированного случайным образом, исследователи добивались постоянного увеличения сопротивления сетки, таким образом, что в последний момент оно стало бесконечным. То есть связь между положительным и отрицательным зажимом генератора тока исчезла. Эта ситуация была названа порогом протекания. Если определить порог протекания как отношение количества разрезанных узлов к их общему числу, то при бесконечно большой решетке он будет равен 0,59. При условии использования трехмерной решетки порог протекания приобретает значение 0,31.
Эта задача получила название задачи узлов. Если же в исследуемой решетке перерезать не узлы, а их соединения (рис. 2), то задача преобразится в задачу связей. Ее решением для бесконечно двумерной решетки с бесконечно большим числом узлов является порог протекания, равный 0,5. Если же обратиться к трехмерной решетке, то ее порог протекания составит 0,25.
Третья задача самая сложная, поскольку наиболее реально отображает исследуемую нами систему и предполагает возможность исчезновения связи как в узлах, так и в их соединениях. Вновь представим себе квадратную решетку и предположим, что каждый квадрат этой решетки, или ячейка, может находиться в двух состояниях — «работы» или «поломки». При этом каждая ячейка занимается с вероятностью р независимо от состояния соседних ячеек. Эта модель называется ячеечной перколяцией. Занятые ячейки либо изолированы друг от друга, либо образуют группы, состоящие из ближайших соседей. Кластер – группа занятых ячеек решетки, связанных с ближайшим соседом по стороне ячейки. Две занятые ячейки принадлежат одному кластеру, если они соединены путем, состоящим из занятых ячеек (рис. 3), в ином случае кластер не существует (рис. 4). Занятым ячейкам соответствуют красные клетки, свободным – синие.
Один из простых способов изучения перколяции основан на использовании генератора случайных чисел. Вычислительная процедура при этом сводится к генерации случайного числа и его сравнению с некоторым порогом р (ячейка решетки считается «рабочей», если случайное число меньше р). Если вероятность рабочего состояния ячейки мала, можно ожидать, что будут присутствовать только небольшие, изолированные кластеры. По сравнению с этим, если р
~ 1, то можно ожидать, что большинство работающих ячеек образуют один большой кластер, который протянется от одной стороны решетки до другой. О таком кластере говорят, что он «перекидывается» через решетку, и называют соединяющим кластером. В нашем случае это обязательное условие для вертикальных стоек ячеек, так как «кубики» не могут висеть в воздухе и должны опираться друг на друга.
В пределе бесконечной решетки существует вполне определенная «пороговая вероятность» р такая, что для р> рс
существует один соединяющий кластер или путь; для р < рс
нет ни одного соединяющего кластера и все кластеры конечны.
С физической точки зрения переход из состояния, в котором существует соединяющий кластер, в состояние, в котором данного кластера не образуется, является математической моделью. Для конечной решетки со стороной n всегда существует ненулевая вероятность того, что будет появляться соединяющий кластер, связывающий одну сторону решетки с другой. Для малых значений р эта вероятность составляет порядка рn. По мере увеличения n данная величина стремится к нулю, и для достаточно малых значений р будут существовать только конечные кластеры. Поскольку нам необходимо применить правило протекания для конечной решетки, мы определим рс(n) как такое значение р,, при котором впервые появляется соединяющий кластер. Для конечной решетки определение протекания произвольно, следовательно, вычисленное выражение рс зависит от критерия протекания. Не особо углубляясь в алгоритм решения этой задачи, скажем, что порог протекания для двумерного массива ячеек составляет 0,34, и всего 0,21 — для трехмерного.
Теперь, вооружившись теорией, мы можем перейти к описанию проекта IBM CIB.
