Среда исполнения Т-системы реализована в виде библиотеки параметризованных классов С++, инкапсулирующих обобщения понятий «переменная», «указатель», «значение» и «величина». «Значение» — это реальные данные, в то время как «величина» — это объект со сложным поведением, описанным ниже. Величины и являются надстроенными ячейками Суперпамяти. Императивная семантика многократного присваивания реализована в виде «перенаправления» переменных и указателей на новую величину в случае необходимости. Взаимодействие между разными потоками вычислений происходит через так называемые «холодные» величины, то есть величины с семантикой однократного присваивания. В то же время, величина, принадлежащая только одному потоку, имеет семантику многократного присваивания — это так называемая «горячая» величина. Величина может быть неготовой — тогда ее значение (т.е. данные) недоступно для потребителей. Поток (процесс), запросивший реальное значение такой величины будет приостановлен до тех пор, пока величина не сделается готовой (синхронизация по типу «поставщик-потребитель»). Таким образом, величины могут быть:
- Горячими неготовыми
- Горячими готовыми
- Холодными неготовыми
- Холодными готовыми
Одна неготовая величина может быть присвоена другой до того момента, как величина-источник получит реальное значение (станет готовой). Операция присваивания неготовых величин реализуется при помощи дополнительного списка: к каждой неопределенной величине может быть привязан список присвоенных ей неготовых величин. Неопределенна величина не провязана в список ожидания никакой другой неготовой величины. Определенной называется величина, либо имеющая реальное значение, либо провязанная в списке ожидания у неопределенной величины.
Неготовые холодные сущности становятся готовыми только после того, как в них будет записано реальное значение. При этом если неготовая величина имеет список связанных с ней определенных неготовых величин, то каждой величине из списка сообщается то же реальное значение
Если неопределенной величине присваивают другую неготовую величину, то происходит «распространение определенности», а именно все определенные неготовые величины, ожидавшие значения от «определившейся» величины, провязываются в список присвоенной неготовой величины.
Стоит также отметить, что «несобственная» ячейка суперпамяти ведет себя как неготовая величина, заставляющая потребителя ждать, пока из сети не приедут реальные данные (готовое значение).
Возможное расширение адресного пространства суперпамяти для поддержки распределенных вычислительных сетей
Предполагается, что в метакластерных решениях потребуется расширение адресного пространства суперпамяти. В этом случае предполагается использовать тип long long вместо long для номера ячейки суперпамяти.
1. Младшие четыре байта будут играть роль номера ячейки в сегменте суперпамяти, как описано выше.
2. Старшие 2 байта будут использоваться как номер в массиве сегментов (рис. 2).
Рис. 2 Расширение адресного пространства суперпамяти
Предполагается, что в реальных применениях будут инициализированы и использованы лишь несколько сегментов. Основную часть обращений к суперпамяти составят обращения к ячейкам в собственном сегменте кластера, поэтому вычисление адреса по номеру сегмента будет осуществляться в два этапа:
- сравнение номера сегмента с номером локального сегмента — возвращается адрес в локальном сегменте в случае совпадения;
- вычисление адреса в массиве указателей сегментов. Неинициализированные элементы массива (сегменты, к которым ни разу не обращались), содержат NULL.
Очевидно, что все ячейки, находящиеся в нелокальных сегментах суперпамяти являются отраженными (или slave) ячейками.
Планирование в OpenTS
Задача планировщика заключается в том, чтобы свести к минимуму время исполнения программы. Это означает, что в каждый момент времени каждый узел кластера занят какой-то работой. Узел простаивает, если его очередь пренатальных задач (ptq) пуста, а все исполняемые задачи находятся в ожидании ресурсов. Таким образом, главная задача планировщика — обеспечить наличие задач в очереди на каждом узле [43].
Постановка задачи
Имеется вычислительная система, состоящая из N узлов. На каждом узле есть множество задач. Задачи делятся на пренатальные и исполняемые (непренатальные). Пренатальные задачи могут перемещаться между узлами кластера, исполняемые — нет. Исполняемые задачи, в свою очередь, делятся на следующие:
- ожидающие неготового значения;
- готовые к исполнению (ожидающие процессорного времени).
Планировщик может предпринимать следующие действия:
- переслать одну или несколько пренатальных задач на другие узлы;
- продолжить одну из исполняемых задач;
- запустить одну из пренатальных задач, тем самым, переводя ее в категорию исполняемых.
Исполняемые задачи могут порождать новые пренатальные задачи. Их количество заранее неизвестно и не зависит от действий планировщика. Задача планировщика — минимизировать общее время исполнения программы.
2.10.2. Алгоритм планирования
Каждый раз, когда планировщик получает управление, он производит следующие действия:
- пересылку части пренатальных задач на другие узлы кластера;
- локальное исполнение задач, куда входит передача управления на одну из готовых к работе исполняемых задач, или, если таких нет, запуск пренатальной задачи.
Далее будет обсуждаться алгоритм первой части, принятие решения о пересылке задач.
С каждой задачей связывается набор из N+1 числа, характеризующий
- вычислительную сложность задачи (1 значение);
- создаваемую нагрузку на коммуникационные каналы (N значений, по одному для каждого узла).
Эта информация может быть получена несколькими путями. Рассматриваются два основных варианта. В первом из них информация может быть получена в виде подсказок планировщику, включаемых в код прикладной программы, и во втором варианте — путем усреднения замеров предыдущих запусков той же Т-функции.
Нагрузка на сеть (сетевая активность задачи) включает в себя две составляющие. Первая — это собственно размер задачи, т. е., объем данных, пересылаемых до ее запуска. Сюда входят аргументы Т-функции и некоторая служебная информация. Объем этих данных известен планировщику — это объем соответствующего задаче класса tfunImpl. Вторая составляющая — это пересылки, вызванные задачей во время ее исполнения. К ним относятся, например, обращения по Т-указателям внутри Т-функции (они могут привести к копированию содержимого Т-переменной с удаленного узла), а также — использование параметров, передаваемых «по указателю». Объем данных, составляющих вторую компоненту, неизвестен заранее и слабо поддается предсказанию (может сильно меняться в разных запусках одной Т-функции). С учетом этого обстоятельства, вторую компоненту разумно оценивать из других соображений, например, большинство Т-задач ведут наиболее интенсивный обмен данными с тем узлом, на котором они были созданы.
Если просуммировать эту информацию по всем задачам на определенном узле, получим время, в течение которого данный узел не будет испытывать недостатка в работе, и общую сетевую активность, которую он будет проявлять в это время. В нашей модели планировщик не имеет никакой информации о том, сколько и каких задач порождает каждая Т-функция. В этих условиях оптимальным поведением будет такое, которое позволяет добиться максимально равномерного распределения имеющихся в системе пренатальных задач по узлам с точки зрения суммарного времени выполнения.
Планировщик использует сегмент суперпамяти для доступа к информации о состоянии очередей на всех узлах кластера. Каждому узлу соответствует ячейка суперпамяти, в которой он размещает суммарную вычислительную сложность пренатальных задач.
Таким образом, каждый узел имеет информацию T1,T2,…,TN о состоянии ptq (очереди пренатальных задач) на всех узлах кластера. В качестве характеристики распределения задач возьмем дисперсию (среднеквадратичное отклонение) этих значений: