Модели памяти: Причина переосмысления параллельных языков и аппаратного обеспечения

Перевод статьи: Sarita V. Adve, Hans-J. Boehm «Memory Models: A Case for Rethinking Parallel Languages and Hardware»

Преамбула

Эра параллельных вычислений для массовго использования уже наступила, но написание корректной параллельной программы все еще остается намного более сложной задачей, чем написание последовательной программы. За исключением отдельных случаев, большинство параллельных программ использует подхода разделяемой (shared) памяти. Модель памяти, которая определяет значение разделяемых переменных, является основополагающим моментом разработки подобным способом. К сожалению, в таком случае приходится выбирать между программируемостью и производительностью, что, очевидно, является областью наиболее подверженной обсуждению как в спецификациях языков программирования, так и в архитектуре аппаратного обеспечения. Повышенное внимание к данному вопросу в конце концов привели к необходимости в подобных дебатах, в которых обсуждается использование популярных языков програмирования, таких как C++ и Java, и опубликованных спецификаций совместимой модели памяти большинства производителей аппаратного обеспечения. Несмотря на то, что подобные дебаты уже сами по себе являются неоспоримым достижением, были выявлены фундаментальные недостатки в современных языках и системах, которые ограничивают дальнейшее развитие безопасного параллельного программирования.

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

Введение

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

Модель памяти, или модель согласованности (consistency) памяти, находится в центре семантики параллелизма программ и систем с разделяемой памятью. Она определяет подмножество значений, для которых разрешено чтение в программе, определяя тем самым базовую семантку разделяемых переменных. Она отвечает на вопрос: Достаточен ли реализованный механизм синхронизации для того,  что бы требуемая операция записи достоверно осуществлялась перед операцией чтения? Могут ли два потока писать в смежные поля памяти в одно время? Должно ли конечное значение быть таким, какое оно было в момент последней записи?

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

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

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

В конце 80х и 90х, данная область получила внимание преимущественно в среде разработчиков аппаратного обеспечения, где многие подходы [2] исследовались в плохой согласованности. Описания коммерческой аппаратной модели памяти имели существенно отличались в точности, включая случаи полного игнорирования отдельного раздела и некоторых отраженных нежеланий изготовителя сделать требуемые пояснения для непрозрачных особенностей использования в будущем. Хотя модель памяти влияет на значение каждой загруженной инструкции в каждом многопоточном приложении, она иногда все еще относится к разделу «системноого программирования» в руководстве по архитектуре.

Еще одним из сложных моментов для архитекторов программного обеспечения было отсутствие прозрачной модели памяти на уровне языков программирования – было непонятно что разработчики программного обеспечения должны ожидать от аппаратного обеспечения с которым работают. Несмотря на это, исследователи, работающие в области аппаратных средств предложили способ избавться от данной проблемы [3], для всеобщего признания было необходимо найти консенсус со стороной разработчиков программного обеспечения. До 2000 года, существовало несколько программных окружений, которые учитывало данную публикацию с относительной степенью совместимости [37], но наиболее распространенные окружения имели невнятные спецификации, которые провоцировали возникновение многих вопросов [29, 9]. Даже если спецификации были достаточно понятны, они часто нарушались в целях повышения производительности [9], что способствовало непониманию многих моментов реализации даже экспертами, и были сложны в изучении.

С 2000 года мы приступили к попыткам четко специфицировать модель памяти на уровне языков программирования, в первую очередь для Java и C++, к попыткам адапатировать подобные модели для C и других языков. В процессе нашей работы, мы должны были решать вопросы возникающие в процессе использования различного аппаратного обеспечения, которые не способствовали созданию прозрачной программной модели. Иногда было сложно найти компромис между простой и удобной програмной моделью и адекватной производительностью на существующем аппаратном обеспечении.

Сегодня, языки программирования и большинство изготовителей аппаратного обеспечения имеют (или планируют) совместимые спецификации моделей памяти. Хотя данный момент является неоспоримым достижением на фоне драматического прошлого, он подвержен фундаментальным недостаткам в существующих параллельных языках программирования и их взаимодействии с аппаратной частью. По прошествии десятилетий потраченных на исследования, до сих пор остается чрезвычайно сложно описывать, скажем, какой уровень допустимой нагрузки можно разрешить для системы без ущерба для действующих гарантий безопасности или реализаций используемых методологий. Для нас, полученный опыт позволил понять, что решение проблем моделей памяти требует существенно новых исследований, охватывающих различные области: параллельные языки, аппаратное обеспечение и все окружение вцелом.

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

Последовательная согласованность

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

К примеру, на рисунке 1 отражена сущность конкуррентного алгоритма Деккера. Программа может быть выполнена путем поочередного выполнения шагов двух потоков различными способами. Формально, каждое и таких способов чередований определяет общий порядок выполнения всех шагов, которые должны выполняться всеми потоками. Этот порядок является согласованным к заданной последовательности программы для каждого потока. Любой доступ к разделяемой переменной «видит» предыдущее значение, сохраненное для переменной при  чередовании.

Первоначально X=Y=0 Красный поток Синий поток X = 1; r1 = Y; Y = 1; r2 = X;

Рисунок 1. Суть Алгоритма Деккера. Может ли r1 = r2 = 0?

Выполнение 1 X=1; r1=Y; Y=1; r2=X; // r1==0; // r2==1; Выполнение 2 Y=1; r2=X; X=1; r1=Y; //r1==1; //r2==0; Выполнение 3 X=1; Y=1; r1=Y; r2=X; //r1==1; //r2==1;

Рисунок 2. Возможные варианты выполнения к рисунку 1

На рисунке 2 представлены три возможные последовательности которые вместе иллюстрируют все возможные финальные значения неразделяемых переменных r1 и r2. Хотя так же могут быть и другие последовательности переключений между потоками, невозможно что бы r1 и r2 были равны 0 в конце выполнения; любое выполнение должно начинатся с первого выражения каждого из потоков, и установленная здесь переменная будет считываться другим потоком в дальнейшем. Следуя Лэмпорту [24], выполнение, которое может трактоваться как чередование ссылается на последовательную согласованность (sequential consistency). Последовательная согласованность дает нам самое простое понимание разделяемых переменных, но предостерегает от некоторых смежных течений.

Во-первых, последовательная согласованность может быть затратной  в реализации. Для рисунка 1, компилятор может, к примеру, изменить порядок двух независимых присваиваний для красного потока, в случае раннего планирвания загрузки для того что бы скрыть возможные задержки. В дополнение, современные процессоры почти всегда используют буфер для хранения, что бы избежать ожидания завершения сохранения, также эффективно изменяет порядок инструкций для каждого потока. Обе оптимизации и на уровне компиляторов и на уровне аппаратного обеспечения в конечном счете могут привести к случаю, когда будет r1==0 и r2==0 и как следствие могут привести к выполнению непоследовательной согласованности. Таким образом, изменение порядка любой пары доступа, чтения переменных из буффера записи, регистрации присвоения, исключение основных подвыражений, исключение избыточного чтения, и многие другие оптимизации процессоров и компиляторов, используемых в системах с одиночным процессором, потенциально могут привести к нарушению последовательной согласованности. [2]

Для того что бы определить, что подобная транформация небезопасна, анализатору компилятора необходимо выполнить небольшую работу (например [43]). Компиляторы, однако, имеют мало информации о разделяемых переменных, используемых разными потоками, делая трудозатраным выполнение подобного анализа перед применением оптимизации, которые мы обязаны выполнить везде. Так же здесь много работы на теоретическом выполнении этих оптимизаций в аппаратном обеспечении, с поддержкой откатов при выявлении актуальных нарушений последовательной согласованости (например [19, 24]). Однако эти идеи относятся к техникам специфичных реализаций (например поддержка решительного предположения (aggressive speculation support)), и изготовители как правило нерасположенны к ним в долгосрочной перспективе (в особености,применительно к компиляторам с непоследовательной согласованностью). Таким образом, большинство современных процессоров и компиляторов не предоставляют последовательной согласованности.

Во-вторых, несмотря на то, что последовательная согласованность выглядит простейшей моделью, она не достаточно проста и не так полезна как это казалось изначально. К примеру, имеет смысл рассуждать о чередовании шагов, только если нам известно об этих шагах. В этом случае, они представляют собой независимое обращение к памяти, на очень низком уровне. Попробуем представить два потока, которые в одно и то же время устанавливают значение 100.000 и 60.000 для разделяемой переменной X на 16-биной машине (за один такт доступ осуществялется только к 16 битам). Финальное значение переменной X при выполнении с «последовательной согласованностью» может быть 125.536 если присваивание значения 60.000 произошло между верхней и нижней половиной присваивания значения 100.000. На более высоком уровне это означает, что значение даже самых простейших операций библиотеки зависит от гранулярности системы, на которой данная библиотека выполняет свои операции.

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

Данные без состояния гонок

Мы можем избежать обе рассмотренные проблемы обратив внимание на то что:

·         Проблеммное преобразование (например изменения порядка операций по доступу к несвязанным переменным на рисунке 1) никогда не влияет на результат в  однопоточных программах, но влияет на результат многопоточных (например, позволяя обоим переменным r1 и r2 рисунка 1 быть установленым в 0)

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

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

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

Мы может сказать, что программа (со специфическими входными данными) позволяет получить состояние гонок, если у нее есть последовательное согласованное выполнение (то есть, порядок чередования выполнения шагов отдельных потоков определен в программе) при котором две простые (несинхронизированные) конфликтующие операции выполняются «одновременно». В нашем случае, две операции выполняются «одновременно» если они следуют друг за другом при чередовании шагов и относятся к различным потокам. Поскольку данные операции выполняются друг за другом при чередовании и мы знаем что они могут с так же хорошо выполнятся и в противоположном порядке; нет чередующихся операций влияющих на порядок.

Что бы убедится, что две несинхронизированные конфликтующие операции не выполнятся одновременно, они должны быть упорядочены посредством синхронизирующих операций чередования. Например, один поток должен освободить блокировку после доступа к разделяемой переменной, а другой поток должен получить блокировку перед обращением к переменной. Хотя, так же можно определить состояние гонок данных как конфликтующий доступ неупорядоченный синхронизацией, как это сделано в Java. Эти определения эквивалентны [1, 12].

Программу, которая не допускает возникновения состояний гонок памяти, называется свободной от гонок. А модель, свободная от гонок гарантирует последовательную согласованность только для программ, свободных от гонок [3, 1]. Для программ, которые допускают сотояния гонок, данная модель не предоставляет никаких гарантий.

Ограничения на состояние гонок не обременительно. В дополнение к блокировкам, которые предназначены для избежания возникновения гонок, современные языки программирования как правило обеспечивают механизм, подобный тому, который в Java носит название изменчивых переменные (volatile variables). Этот механизм объявляет, что определенные переменные или поля могут использоваться для синхронизации между потоками. Конфиктующий доступ к таким переменным может произойти одновременно – так как они явно определены как синхронизированные (в отличие от обычных, несинхронизированных), они не являются источниками гонок.

Для того что бы реализовать пример, показанный на рисунке 1 корректно без возникновения состояний гонок, нам необходимо просто идентифицировать разделяемые переменные X и Y как синхронизированные переменные. Это потребовало бы любой реализации, которая гарантировала бы последовательную согласованность, несмотря на одновременный доступ. Также потребовалась бы реализация гарантий цельного (неделимого) выполнения операций синхронизованного доступа; если 32-битное число используется для синхронизации, не должно быть доступа к нему как к двум 16-битным половинкам.

Этот решение «последовательной согласованности для програм свободных от состояний гонок» облегчает проблему обсуждаемую для случая чистой последовательной согласованости. Наиболее важные оптимизации процессора и компилятора остаются доступными для обычных операций – осторожность должна иметь место преимущественно только при явно указанном синхронизированном доступе, в результате которого оптимизация может повлиять на выполнение программы. Далее, несинхронизированные секции кода выполняются атомарно и подобные требования, призывающие явно указывать конкуррентный доступ, делает более простым понимание кода и человеком и компилятором. Этот поход описан более детально в [11].

Устойчивость от состояний гонок не предоставляет возможности для осуществления оптимизаций для однопоточных программ. Практически, оптимизации, касающиеся копирования значения разделяемой перменной в саму себя,  то есть выполнения присваивания x = x, где значение x не может быть переписано в другими способами, остаются некорректными. Это главным образом реализованно в определенных контекстах [9].

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

Промышленная практика и эволюция

Аппаратные модели памяти

Большинство аппаратного обеспечения поддерживает «смягченные» модели (relaxed models) которые являются более слабыми, чем последовательная согласованность. Эти модели используют подходы, в основе которых лежит реализация (implementation-centric view) или производительность (performance-centric view). В них желаемые процессорные оптимизации являются базой спецификации модели [2]. Типичные движущие оптимизации смягчают требования к порядку последовательной согласованности программы. Например, TSO (опция разделения времени) процессоров SPARC гарантирует, что доступы потока к памяти будут видны другим потокам в порядке заданном в программе, за исключением случаев, когда операция чтения следует за операцией записи.

Подобные модели дополнительно предоставляют ограничивающие инструкции, позволяющие программистам явно устанавливать порядок, который не может быть гарантирован иным способом; например программисты TSO могут установить ограничение между операциями записи и чтения потока для того что бы быть уверенным в том, что в процессе выполнения заданный порядок будет сохранен. Подобный стиль спецификации с заданием порядка и ограничений на уровне программы прост, но многие его нюансы могут не отвечать требованиям [1, 2]. Во-первых, этот стиль предполагает, что операция записи атомарна и неделима, и она видна всем потокам именно так. Однако, на рисунке 3 проиллюстрирован случай, когда осуществляемая процессором операция записи может быть видна разным потокам в разное время через используемые буфферы записи и разделяемый кэш. Добавление подобной оптимизации увеличивает сложность спецификации модели памяти. Таким образом, полная спецификация TSO, в которую включены самые простые атомарные оптимизации, оказывается более запутанной чем простое описание продемонстрированное выше. Модель PowerPC реализует более решительную форму оптимизации, со спецификацией, которая выглядит комплексной и сложной для интерпретации даже для экспертов. Документация x86 для Inter и AMD была неоднозначной в этом плане; однако недавние обновления добавили пояснения к имеющимся неоднозначностям, хотя эти обновления и остаются неофициальными.

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

Первоначально X = Y = 0; Ядро 1 Ядро 2 Ядро 3 Ядро 4 X = 1; Y = 1; r1 = X; ограничение r2 = Y; r3 = Y; ограничение r4 = X; Может ли в результате быть r1=1; r2=0;r3=1; r4=0; нарушая атомарность операций записи?

Рисунок 3. Процессор не может выполнить атомарные и неделимые операции записи. Предположим в порядок программы добавлено ограничение. Положим кэши третьего и четвертого ядра имеют X и Y. Две операции записи инициируют сброс данных кешей. Это может привести к изменению порядка кэшей, формируя показанный результат и приходя к ситуации, когда оба обновления X происходит до и после обновления Y.

Первоначально X = Y = 0; Ядро 1 Ядро 2 r1 = X; if(r1==1) { Y = 1; } r2 = Y; if(Y==1) { X = 1; } Допустимо ли r1 = r2 = 1?

(a)

Первоначально X = Y = 0; Ядро 1 Ядро 1 r1 = X; Y = r1; r2 = Y; X = r2; Допустимо ли r1 = r2 = 42?

(b)

Рисунок 4. Тонкость с зависимостями контроллирования (a) и данных (b). Допустим, при чтении ядром 1 значения X мы получим 1 и предположим выполним операцию записи в Y. Ядро 2 также осуществляет запись в X. Обе операции чтения теперь дадут 1, создавая «самозаполняемое» предположение или «обусловленный» цикл. В случае с одним ядром, нету зависимости контроллирования, так как предположение корректно; однако, большинство программистов не будут ожидать такого результата (данный код на самом деле является свободным от состояния гонок так как здесь нету возникновений состояния гонок в процессе выполнения последовательной согласованности). Часть (b) показывает аналогичный случайный цикл с зависимостями данных. Ядро 1 может полагать что X = 42 (например, используя предположение о значении, основанное на предыдущем сохраненном значении) и (что любопытно) пишет значение 42 в Y. Ядро 2 читает это и пишет 42 в X, таким образом доказывая предположение и создавая случайный цикл который генерирует значение (42). К счастью, в наши дни нету процессоров которые ведут себя таким образом, но спецификация модели памяти должна отражать эту особенность.

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

4.2 Модели памяти высокоуровневых языков

Язык Ada очевидно был первым широко распространенным высокоуровневым языком, который предоставил первый класс для поддержки параллельного программирования с использованием разделяемой памяти. Хотя подход используемый в языке для синхронизации потоков изначально был немного отличным от последующего дизайна более поздних языков, он был необыкновенно продвинутым в плане семантики памяти [37]. Он использовал стиль, похожий на стиль свободный от состояний гонок, требуя что бы корректные программы были хорошо синхронизированными; при этом не требуя полного представления о понятии «хорошо синхронизированного» и оставляя неопределенным поведение подобных программ.

Позже, пока не появилась Java, основные языки программирования не предоставляли качественной поддержки для потоков, и программирование разделяемой памяти было возможно только с использованием библиотек и API, таких как потоки POSIX и OpenMP. Наша предыдущая работа описывает почему подход применения дополнительных библиотек потоков не удовлетворителен [9]. Без реального определения языка программирования в контексте потоков, остается непонятным вопрос, какие трансформации совешаемые компилятором являются легальными, и таким образом, что программист может предполагать. Все-таки, спецификация потоков POSIX демонстрирует модель приближенную к свободной от состояния гонок, хотя здесь есть несколько несовместимых аспектов, с сильно различающимися интерпретациями даже между экспертами учавствующими в обсуждениях коммитета по стандарту. Модель OpenMP также не прозрачна, и в своем большинстве основана на инструкциях, аналогичных инструкциям ограничения в аппаратной модели, с соответствующими недостатками.

4.2.1 Модель памяти Java

Язык Java предоставляет первоклассную поддержку для потоков с разделением специально предназначенным для ее модели памяти. Пав (Pugh) показал что данная модель сложна в интерпретации и плохо разбиваемая – основные оптимизации компилятора были запрещены и во многих случаях модель демонстрировала неоднозначное или неопределенное поведение [29]. В 2000, Sun собрала экспертную группу для того что бы провести ревизию модели с помощью сообщества [30]. Усилия координировались через открытую рассылку по электронной почте куда были привлечены различные участники, представляющие вендоров аппаратного обеспечения, разработчиков программного обеспечения, исследователей и практиков.

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

Однако, свобода от состояний гонок невозможна для Java. Поскольку Java считалась безопасным и защищенным языком, она не могла позволить произвола для состояний гонок. В особенности, Java должна поддерживать ненадежный (untrusted) код как часть надежного приложения и таким образом должна ограничивать ущерб причиненный состоянием гонок в ненадежном коде. К сожалению, идея безопасности, защищенности и «ограниченного ущерба» в многопоточном контексте не были как следует определены. Проблемой с определением модели памяти Java было формализовать эти понятия, таким образом что бы они минимально воздействовали на гибкость системы.

Рисунок 4(b) показывает эти случаи. Программа имеет состояние гонки и она некорректна. Однако, Java не может позволить операцию чтения для того что бы возвратить значение (return value out-of-thin-air) (как в случае с числом 42) поскольку должен быть найдено компромис для удовлетворения условий безопасности и защищенности. Например, было бы невозможно гарантировать что подобный ненадежный код не может вернуть пароль к которому не должно быть доступа. Подобные сценарии появляются для того, что бы нарушить любое обоснованное ожидание и ни один текущий процессор не деалет этого. Тем не менее, модель памяти должна формально запрещать подобное поведение, так что бы будущие процессоры также избегали этого.

Запрещение подобных нарушений каким то способом которые не будет способствовать одновременному запрещению других оптимизаций чрезвычайно сложная задача. Рисунок 5 демонстрирует пример в котором также возникает нарушение обусловленности (causality violation), но оно разрешено основной оптимизацией компилятора исключения избыточного чтения. После множественных предложений и пяти лет оживленных дискуссий, текущая модель была принята как наилучший компромис. Эта модель позволяет добиться результата продемонстрированного на рисунке 5, но не такого который продемонстррован на 4(b). К сожалению, эта модель очень сложна, она имеет несколько неожиданных поведений, и как было недавно показано не лишена ошибок. Мы предоставляем небольшой пример для модели представленной ниже и направляем читателей к [26] за полным описанием.

Первоначально X = Y = 0; Оригинальный код Поток 1 Поток 2 r1 = X r2 = X if (r1 == r2) { Y = 1} r3 = Y X = r3 После преобразований компилятора Поток 1 Поток 2 Y = 1 r1 = X r2 = r1 if(true); r3 = Y X = r3 Допустимо ли r1 = r2 = r3 = 1?

Рисунок 5. Исключение избыточного чтения может спровоцировать появление нарушения обусловленности, но должно быть разрешено. Для потока 1, компилятор может исключить избыточное чтение переменной X, заменив r2=X на r2=r1.Это позволит прийти к заключению, что выражение r1==r2 всегда корректно, делая запись в Y безусловной. Потом компилятор может сместить операцию записи что бы она выполнялась перед чтением X так как зависимости не нарушены. Последовательная согласованность позволяла бы обеим операциям чтения X и Y возвращать 1 в новом но не в оригинальном коде. Этот результат для оригинального кода появляется для нарушения обусловленности поскольку требуется самодоказываемая предполагаемая операция записи Y.

Общим для рисунков 4(b) и 5 является операция записи, которая выполняется раньше чем она выполнялась бы в случае наличия последовательной согласованности. Примеры отличаются тем, что для предполагаемой операции записи в конце (Y=1), есть несколько последовательных согласованных выполнений , где они выполняются (выполнение где обе операции чтения X возвращают 0). Для рисунка 4(b), не может быть последовательного согласованого выполнения для Y=42. Это мнение, с помощью которого определяется возможность предполагаемой операции записи в приемлимой форме является базисом обусловленности в модели Java и определение «хорошего поведения»   ключевой источник сложности.

Модель Java проверяет допустимость выполнения путем «совершения» одной или более операций доступа к памяти в определенное время – допустимость требует, что бы все операции доступа были совершены (в любом порядке). Осуществление операции записи раньше требуемого времени (до того как эта операция определена в порядке программы) требует, что бы она выполнялась в контексте «хорошего поведения», где (неформально) (1) выполненные операции доступа имеют похожую синхронизацию и взаимоотношения состояний гонок во всех предыдущих выполнениях и (2) операции записи которые должны выполнится не зависят от операций чтения, которые возвращают значения из состояний гонок. Эти условия убеждают, что будущие состояния гонок не будут использоваться для подтверждения предполагаемой операции записи которая вдальнейшем может подтвердить последующие состояния гонок.

Ключевой причиной сложности модели  Java является тот факт что она непрактична – доступ в будущем сможет определить является ли текущий доступ допустимым. Далее, много возможных будущих выполнений должны быть рассмотрены для определения их легальности. Этот выбор в будущем (хорошее поведение) выполнении также предоставляет некоторые неожиданные результаты. На самом деле, как обсуждалось в [26], если код одного потока совмещен («inlined») с другим потоком, то такой код может реализовывать больше поведений, чем оригинальный код. Таким образм, подобный эффект является недопустимым для модели Java (даже если не предполагается наличия синхронизации и тупиков (deadlock)). На практике, запрещенные оптимизации сложно реализовать и это не является значимым для ограничения производительности. Данное поведение, однако, не интуитивно, с другими причастностями – оно возникает изза того, что некоторые состояния гонок в оригинальном коде могут перестать быть такими состояниями в «inlined» коде. Это значит, что в момент определения совершения ранней операции записи, операция чтения при выполнение с «хорошим поведением» имеет больше выбора для возврата значений чем раньше (поскольку существует меньше состояний гонок), что выливается в новые поведения.

Как правило, увеличение синхронизации в модели Java может привести к новому поведению, даже несмотря на то что большая синхронизация условно приводит к возможным выполнениям. Недавно, было показано, что  по подобным причинам, добавление неподходящих операций чтения или удаление изыбточных операций чтения иногда также может добавить новое поведение, и данные свойства имеют более серьезные последствия чем предполагалось ранее [33]. На практике, некоторые оптимизации которые были разрешены моделью памяти Java в действительности являются запрещенными текущей спецификацией.

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

Модель Java управлялась как правило существующим набором тестовых случаев [30], основанных на неформальном преобразовании кода, которые были или наоборот не были желаемыми. Пока существует возможность изменить модель Java, остается нежелательным что наша спецификация поведения многопоточных программ опиралась бы на таком сложном и неустойчивом основании. Вместо этого, секция 6 пропагандирует фундаментальное переосмысление нашего подхода.

4.2.2 Модель памяти С++

Ситуация с C++ существенно отличается от той, что мы видим в случае с Java. Сам по себе язык не предоставляет поддержки потоков. Несмотря на это, они широко применяются, как правило посредством использования дополнительной библотеки, реализующей требуемую функциональность, как pthread [20], или соответствующие реализации Microsoft Windows. К сожалению важнейшие спецификации, например комбинации стандартов C и C++ в купе со стандартом Posix, оставляют нераскрытым вопросы правил управления разделяемыми переменными [9]. Это делает для создателей компиляторов непонятным точное определение того что им нужно реализовать, приводя в результате к очень случайным сбоям для которых сложно найти виноватого, и что наиболее важно, делает сложным процесс обучения параллельному программированию, поскольку даже эксперты не смогут согласится с некоторыми базовыми правилами, такими как может ли ситуация отображенная на рисунке 4(a) привести к состоянию гонки данных (Правильный ответ: Нет).

Мотивированные, данными наблюдениями, мы в 2005 году мы начали работу над моделью памяти для C++. Усилия в конечном счете были увеличены для включения определения атомарных операций (синхронизация аналогичная Java) и API для потоков соответственно. Это часть существующего черновика [22], для следующей ревизии С++. Следующий стандарт C предполагает содержать очень похожую модель памяти, с очень похожими атомарными операциями.

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

·         Модель  языка программирования более слабая чем свбода от гонок данных вероятно не пригодна для использования большей частью сообщества программистов. Ранняя работа [10] отмечает данный момент, к примеру, даже создатели библиотеки реализующей работу с потоками часто остаются сбитыми с толку когда приходится явно иметь дело с упорядочиванием операций непосредственно в памяти. Главное усилие было помещено на попытки разработать более слабую, но сравнительно простую и пригодную для использования модель. Мы не чувствуем что добились успеха.

·         В некоторых архитектурах, в особенности на некоторых реализация PowerPC, свобода от гонок данных, является самой трудозатратной задачей. (в свете современных спецификаций (2009), подобная стоимость других, в особенности x86, более скромная, и ограничена в большинстве своем атомарными (C++) или изменчивыми (volatile)(Java) операциями хранения).

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

Так как C++ не поддерживает выполнение кода в песочнице (sand-box), черновой стандарт C++ может и оставляет семантику программы с гонками данных абсолютно неопределенной, эффективно делая написание таких программ некорректным. Как мы отмечали в [12], это имеет некоторое количество в большинстве своем производительных, с преимуществами и большим отражением в существующих реализациях компиляторов.

В дополнение к моментам отраженных в секции 5, следует отметить что это действительно толкает моменты Java в намного меньший и темный угол спецификации; точно такие же моменты всплывают, если мы перепишем рисунок 4(b) с помощью атомарных операций C++ и использованием операций по низкоуровневому упорядочиванию порядка операций с памятью. Наше текущее решение этой проблемы проще но не такое элегантное как в Java. В отличие от Java, оно затрагивает небольшое количество скрытых вызовов библиотеки, а не доступов к памяти.

С моделью памяти Java, мы чувствуем, что хотя это решение использует компромис, это важный шаг вперед. Оно прозрачно устанавливает свободу от состояний гонок как ключевую гарантию что сможет понять любой прогрммист. Оно точно определяет, что создает гонки данных. Оно в конченом счете решает простой вопрос: Если значения x.a и x.b установлены одновременно, то будет ли это гонной данных? (Нет, пока они являются частью той же смежной последовательности биовых полей.) Поступая таким образом, просто определить недостатки существующих компиляторов которые мы сейчас сможем исправить.

4.3 Примирение  моделей языков программирования и аппаратного обеспечения

На всем протяжении этого процесса, постоянно становилось понятно, что существующие аппаратные модели и инструкции ограничения часто являются в лучшем случае минимальным аналогом моделей памяти языков программирования, особенно с учетом volatile полей Java и атомарных объектов C++. Всегда возможно реализовать подобную синхронизацию переменных, отображением каждой из них на блокировку, и выполнением и освобождением соответствующей блокировки контролирующей все операции доступа. Однако, подобный подход добавляет сотни избыточных циклов для каждой операции доступа, особенно учитывая тот факт, что доступ через блокировку может приводить к пропускам кеша (cache misses), даже если задействованы только операции чтения. 

Изменчивые (volatile) и атомарные переменные как правило используются для избежания использования блокировок для именно этих случаев. Типичное применение  заключается в использовании флага, которые идентифицирует была ли проинициализирована структура данных предназначенная только для чтения. Поскольку инициализация осуществляется только один раз, практически все операции доступа просто читают значение атомарного/изменичивого флага, тем самым избегая необходимости использования блокировки. Применение блокировки для доступа к флагу лишает преимущества данного подхода.

Однако, на аппаратном обеспечении где атомарность операций записи не такая строгая (см рисунок 3), часто становится непонятно возможны ли более эффективные (чем применение блокировок) отображения; даже полностью ограниченная реализация может не обладать последовательной согласованностью. Даже на другом аппаратном обеспечении существуют видимые несоответствия, вызвание в большинстве случаев недостатком хорошего понимания модели языка программирования когда было спроектированно аппаратное обеспечение. На x86 почти достаточно отображать синхронизации загрузок и сохранения на обычные инструкции загрузки и сохранения. Аппаратное обечпечение предоставляет твердые гарантии, того что переупорядочивание обычных операций с памятью синхронизированными операциями не видимо. Однако, нельзя предотвратить переупорядочивание синхронизированного сохранения следующее за синхронизированной загрузкой; таким образом данная реализация не предотвращает неккорректного результата для рисунка 1.

Это может привести к замене синхронизированной операции сохранения на обычныую инструкцию сохранения за которой следует существнное ограничение. Исключительной целью данного ограницения является защита от переупорядочивания синхронизированного сохранения и последующей операции синхронизированной загрузки. На практике подобные синхронизированные загрузки вряд ли будет находится настолько близко (алгоритм Деккера как правило не используется) что бы действительно ограничить аппаратное обеспечение. Но только инструкция ограничения (fence) ограничивает все случаи переупорядочивания памяти, включая случай, когда используются несинхронизированные операции доступа, добавляя таким образом излишнее ограничение. Решением получше будет вариант с привлечением механизма нахождения различий между двумя типами загрузок и сохранения (обычные и синхронизированные), как например инструкции Itanium ld.acq и st.rel [21]. Это, однако, требует изменения набора инструкций архитектуры, что в большинстве случаев является сложным предложением.

Мы подозреваем что нынешняя ситуация делает инструкции ограничения более дорогими чем необходимыми, по очереди мотивируя дополнительную сложность на уровне языков программирования как в случае с низкоуровневыми атомарными сущностями (atomic) C++ или lazySet() в Java.

Урок закончен

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

Отладка

Случайное наличие состояния гонки данных приводит не «неопределенному поведению», которое часто принимает форму неожиданных результатов позже в последующем процессе выполнения программы, намного позже чем на самом деле произошла гонка данных, повлекшая повреждение данных. Хотя обычный мгновенный результат состояния гонки данных не ожидается, и хотя происходит операция чтения незафиксированных значений или операция записи несовместимлого результата, мы отмечаем в [12], что прочие результаты, такие как непреднамеренные разветвления (wild branches) так же возможны в качестве результата оптимизаций компилятора, который ошибочно предполагает что состояния гонок данных отсутствуют. Поскольку подобные случаи сложно воспроизвести, корневую причину подобного некорректного поведения часто сложно определить, и на исправление подобных дефектов могут уйти недели. Многие программные средства призванные отлаживать подобные ситуации (например CHESS [27], RaceFuzzer[32]) также предполагают наличие последовательной согласованности, что ограничивает их полезность.

Производительность синхронизированных переменных на нынешнем аппаратном обеспечении.

Как уже обсуждалось, проверка на наличие последовательной согласованности в присутствии volatile  для Java и atomic для C++ для нынешнего аппаратного обеспечения может дорого обходится. Как результат, и С++ и в меньшей степени Java должны были обеспечить более дешевую альтернативу которая сильно усложняет модель для экспертов, пытающихся использовать ее.

Ненадежный код

В ненадежном (untrusted) коде нету способа убедится в отсутствии состояний гонок данных. Таким образом, эта модель недостаточна для таких языков как Java.

Из нашего опыта можно извлечть недвусмысленный урок – для программ с состояниями гонок данных очень тяжело определить семантику, которую просто понимать и удерживать желаемую гибкость системы. За время развития модели памяти Java, ее сложность, и последующее развитие неожиданных поведений, далеки от желаемого. К сожалению, мы знаем от том что альтернативной спецификации, которая была бы простой в использовании нету. Второе, правила для ослабления гарантий отсутствия гонок данных для лучшего соответствия нынешней аппаратной составляющей, как скажем низкоуровневые atomic из C++, так же более сложные чем этого хотелось бы.

Есть только один очевидный путь для улучшений – исключить потребность в выходе за рамки гарантий свободы от гонок данных:

•          Ликвидировать мотивацию в повышении производительности и

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

Выводы для языков программирования

Несмотря на драматическое схождение в дебатах по моделям памяти, достигнутые результаты приводят к следующему выбору: язык программирования, который позиционируется как язык обладающий сильной безопасностью и надежными параметрами, но не имеющий прозрачного определения какое значение может быть возвращено при выполнении операции чтения разделяемой памяти (случай Java). Против языка с прозрачной семантикой, но требующий избегания надежных параметров обещанных языком, таким как Java (случай C++). К сожалению современное программное обеспечение требует и параллельность и надежность, и потребность выбора между ними недопустимо.

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

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

Двигаясь дальше, мы верим, что для того что бы сделать возможным «параллелизм для масс» нужно разработать и продвигать послушную модель разделяемой памяти (disciplined shared-memory model), которая:

•          достаточно проста для того что бы быть легка в обучении для неопытных новичков, то есть, минимально обеспечивать последовательную согласованность для программ которые подчиняются требуемому порядку;

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

•          быть достаточно универсальной для реализации важных параллельных алгоритмов и паттернов, и

•          Обладать высокой и масштабируемой производительностью.

Многие предыдущие попытки,  главной целью которых было увеличение продуктивности разработчиков находили способы реализаций уровней абстракций работы с потоками; например Cilk [18], TBB [23], OpenMP [36], недавний язык HPCS [25], другие высокоуровневые библиотеки, фреймворки, и API такие как java.util.concurrent и библиотеки boost для C++, хороши как и другие специфичные для конкретной области. Пока приведенные решения преодолевают свой длинный путь по нарправлению к упрощению трудностей для гармоничной реализации параллелизма, наши аргументы основанные на модели памяти являются более глубокими – мы приводим доводы в пользут того, что, по крайней мере сейчас и в недалеком будущем, невозможно обеспечить рациональную семантику для языка которая допускала бы наличие состояний гонок памяти и возможно более фундаментальные проблемы. В действительности, все примеры которые были нами приведены или предоставляют непрозрачную модель или страдают от подобных ограничений как в C++/Java.  Следовательно, эти подходы, не реализуют требований принуждения модели. Похожим образом, транзакционная память обеспечивает высокоуровневый механизм для атомарности, но модель памяти в настоящем не-транзакционном коде сталкивается с теми же проблемами, которые описаны здесь [35].

В сердце наших намерений относительно послушной модели лежат вопросы какая «посушность» требуется и как к ней принуждать? Краткосрочным, переходным путем является продолжение работы со свободой от гонок данных и фокусирование на иследовании вопросов принуждения. Идеальное решение для языков программирования это ликвидировать гонки данных с помощью дизайна (например [13]); однако, наши семантические сложности можно избежать даже динамическими способами (например [16] или  [17]) которые замещают все случаи гонок данных соответствующими исключеними (Есть и другие более быстрые техники динамического определения гонок данных, предназначенные в основном для отладки, но они не гарантируют совершенной точности, как здесь требуется.)

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

Следовательно, ценной послушности является гарантия детерминированности по умолчанию; когда требуется недетерминированность, она должна запрашиваться явно и не должна персекаться с детерминированными гарантиями для остальных фрагментов программы [7]. Здесь много предшествующей работы над детерминированными параллельными данными, фуникцональными и актерскими языками. Мы сфокусированы на универсальных усилиях которые продолжают использовать широко распространенные практики программирования, и сложные структуры данных, основанные на указателях. Подходы, базирующиеся на особенностях языков программирования, с подобными целями включают Jade [31] и более новый Deterministic Parallele Java (DPJ) [8]. В часности DPJ предлагает тип основанный на регионе и эфективную систему для семантики с детерминированностью по умолчанию – название «регионы» отделяет разделы кучи и для каждого метода выполняет сбор информации какой регион использовался в операциях записи и чтения каждым методом. Вместе с упорядоченной структурой параллельного контроля, компилятор легко может использовать полученную суммарную информацию для того, что бы убедится что не произошло неупорядоченных конфликтных операций досутпа и программа детерминирована. Недавние результаты показывают, что DPJ можно применять для большого количества программ и сложных структур данных получая производительность сравнимую с кодом потоков [8].

Так же наблюдался прогресс в методах времени исполнения (runtime methods) для детерминированности [15, 28, 4, 5].

Оба подхода  имеют свои плюсы и минусы и все еще требуют дополнительных исследований перед массовым применением. Подход основанный на использовании языка программирования должен устанавливать, что он достатчно выразителен и не потребует чрезмерных усилий разработчика. Для ранних, новые техники являются обещающими, но пока не более того. Для более поздних, DPJ пытается облегчить бремя путем использования похожего базового языка (Java на данный момент) и обеспечивая полуавтоматические средства для предположений требуемых аннотаций программиста [38]. Далее, аннотации языка такие как эффективная суммарная информация операций чтения и записи DPJ являются значимой документацией – они  способствуют увелчиению жизненного цикла для модулярности, поддерживаемости, спорной компенсации за усилия разработчика. В конечном счете, выгода статических подходов выражена отсутствием оверхеда и сюрпризов во время исполнения.

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

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

Выводы для аппаратного обеспечения

Как было рассмотрено в разделе 4, нынешние аппаратные модели памяти неполностью соответствуют даже нынешним программным (свободным от состояний гонок) моделям памяти. Изменения ISA для того что бы определять отдельные операции загрузки и сохранения как синхронизации могут решить некоторые краткосрочные проблемы. Однако установленные изменения ISA сложно изменить, особенно в случае, когда существующий код работает вцелом как нужно и недостаточно опыта для документирования преимуществ котороые могут быть получены после изменений.

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

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

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

Мы видим эти сложности как возможность не только решить проблемы, обсуждаемые в данной публикации, но делая таки образом, мы ожидаем добиться более эффективных программного и аппаратного обеспечения. Во-первых, мы верим что процессоры у которых будет поддержка программных моделей будут более эффективными чем аналогичные программные решения. Это наблюдение уже лежит в основе работы по моделям смягченной аппаратной согласованности (relaxed hardware consistency model) – мы надеемся что различия нынешенего времени приведут к совместной эволюции программных и аппаратных моделей, а не к модификациям каждой из моделей в отдельности которые могут обеспечить более эффективные решения. Во-вторых, аппаратные исследования для поддержки программных моделей также будут чрезвычайно критичными. Аппаратная поддержка может использоваться для эффективного принуждения требуемого порядка тогда как статических подходов оказывается недостточно; например путем непосредственного определения нарушений порядка и/или используя эффективные стратегии песочниw (sandbox) для ненадежного кода.

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

Выводы

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

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

Благодарности

На эта публикацию сильно повлияли взаимодействия и дискуссии с коллегами на протяжении долее тридцати лет.  Нам чрезвычайно приятно поблагодарить Марка Хилла (Mark Hill) за совместную разработку подходов свободных от состояний гонок и другой фундаментальной работы, Курош Гарачерлу (Kourosh Gharachorloo) за аппаратные модели, Джереми Мэнсона (Jeremy Manson) и Билла Пага (Bill Pugh) за модель Java, Лоуренса Кроула (Lawrence Crowl), Пола МакКини (Paul McKenney), Кларка Нельсона (Clark Nelson) и Герба Саттера (Herb Sutter) за модель C++, и Викрама Адве (Vikram Adve), Роба Боччино (Rob Bocchino) и Марка Снира (Marc Snir) за последующую работу по упорядоченным программным моделям памяти и их принуждениям. Мы бы хотели поблагодарить Дуга Ли (Doug Lea) за бесчисленные дискуссии и продолжительные одобрения запечатать конверт. Напоследок, мы бы хотели поблагодарить Викрама Адве (Vikram Adve), Роба Боччино (Rob Bocchino), Лоуренса Кроула (Lawrence Crowl), Марка Хилла (Mark Hill), Дуга Ли (Doug Lea), Джереми Мэнсона (Jeremy Manson), Пола МакКини (Paul McKenney), Брэйтина Саха (Bratin Saha) и Роба Шрейбера (Rob Schreiber) за комментарии к черновику данной работы. Сарита Адве (Sarita Adve) в настоящее время финансируется корпрорациями Intel и Microsoft через Исследовательский Центр Универсальных Параллельных Вычислений  Иллинойса.

Ссылки

[1] S. V. Adve. Designing Memory Consistency Models for Shared-Memory Multiprocessors. PhD thesis, University of Wisconsin- Madison, 1993.

[2] S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66–76, 1996.

[3] S. V. Adve and M. D. Hill. Weak ordering—A new definition. In Proc. 17th Intl. Symp. Computer Architecture, pages 2–14, 1990.

[4] M. D. Allen, S. Sridharan, and G. S. Sohi. Serialization sets: a dynamic dependence-based parallel execution model. In Proc. Symp. on Principles and Practice of Parallel Programming, 2009.

[5] E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: Safe Multithreaded Programming for C/C++. In OOPSLA, 2009.

[6] C. Blundell, M. M. K. Martin, and T. Wenisch. Invisifence: performance-transparent memory ordering in conventional multiprocessors.In Proc. Intl. Symp. on Computer Architecture, 2009.

[7] R. Bocchino et al. Parallel programming must be deterministic by default. In Proc. 1st Workshop on Hot Topics in Parallelism, 2009.

[8] R. Bocchino et al. A type and effect system for deterministic parallel java. In Proc. Intl. Conf. on Object-Oriented Programming, Systems,Languages, and Applications, 2009. to appear.

[9] H.-J. Boehm. Threads cannot be implemented as a library. In Proc.Conf. on Programming Language Design and Implementation, 2005.

[10] H.-J. Boehm. Reordering constraints for pthread-style locks. In Proc.12th Symp. Principles and Practice of Parallel Programming, pages173–182, 2007.

[11] H.-J. Boehm. Threads basics. http://www.hpl.hp.com/personal/Hans_Boehm/threadsintro.html, July 2009.

[12] H.-J. Boehm and S. Adve. Foundations of the C++ concurrency memory model. In Proc. Conf. on Programming Language Design and Implementation, pages 68–78, 2008.

[13] C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In Proc. Intl.Conf. on Object-Oriented Programming, Systems, Languages, and Applications, 2002.

[14] L. Ceze et al. BulkSC: Bulk Enforcement of Sequential Consistency.In Proc. Intl. Symp. on Computer Architecture, 2007.

[15] J. Devietti et al. DMP: Deterministic shared memory processing.In Proc. Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 85–96, Mar.2009.

[16] T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: a race and transaction-aware java runtime. In Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation, pages 245–255, 2007.

[17] C. Flanagan and S. Freund. FastTrack: Efficient and precise dynamic race detection. In Proc. Conf. on Programming Language Design and Implementation, 2009.

[18] M. Frigo, C. E. Leiserson, and K. H. Randall. The implementation of the Cilk-5 multithreaded language. In Conference on Programming Language Design and Implementation (PLDI), pages 212–223, 1998.

[19] K. Gharachorloo, A. Gupta, and J. Hennessy. Two Techniques to Enhance the Performance of Memory Consistency Models. In Proc.Intl. Conf. on Parallel Processing, pages I355–I364, 1991.

[20] IEEE and The Open Group. IEEE Standard 1003.1-2001. 2001.

[21] Intel. Intel Itanium Architecture: Software Developer’s Manual, jan 2006.

[22] ISO/IEC JTC1/SC22/WG21. ISO/IEC 14882, programming language - C++ (committee draft). http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2800.pdf, 2008.

[23] James Reinders. Intel(R) Threading Building Blocks: Outfitting C++ for Multi-core Parallelism. O’Reilly, 2007.

[24] L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers,

C-28(9):690–691, 1979.[25] E. Lusk and K. Yelick. Languages for high-productivity computing:The DARPA HPCS language project. Parallel Processing Letters,17(1):89–102, 2007.

[26] J. Manson, W. Pugh, and S. Adve. The Java memory model. In Proc.Symp. on Principles of Programming Languages, 2005.

[27] M. Musuvathi and S. Qadeer. Iterative context bounding for systematictesting of multithreaded programs. In Conf. on Programming Language Design and Implementation, pages 446–455, 2007.

[28] M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: Efficient deterministic multithreading in software. In Proc. Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Mar. 2009.

[29] W. Pugh. The Java memory model is fatally flawed. Concurrency -Practice and Experience, 12(6):445–455, 2000.

[30] W. Pugh and the JSR 133 Expert Group. The Java memorymodel. http://www.cs.umd.edu/~pugh/java/memoryModel/and referenced pages, July 2009.

[31] M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of jade. ACM Transactions on Programming Languages and Systems, 20(3):483–545, may 1998.

[32] K. Sen. Race directed random testing of concurrent programs. In Conf. on Programming Language Design and Implementation, 2008.

[33] J. Sevcik and D. Aspinall. On validity of program transformations in the java memory model. In ECOOP 2008, pages 27–51, 2008.

[34] D. Shasha and M. Snir. Efficient and correct execution of parallel programs that share memory. ACM Transactions on Programming Languages and Systems, 10(2):282–312, April 1998.

[35] T. Shpeisman et al. Enforcing isolation and ordering in STM. In Conference on Programming Language Design and Implementation (PLDI), 2007.

[36] The OpenMP ARB. OpenMP application programming interface: Version 3.0. http://www.openmp.org/mp-documents/spec30.pdf, May 2008.

[37] United States Department of Defense. Reference Manual for the Ada Programming Language: ANSI/MIL-STD-1815A-1983 Standard 1003.1-2001, 1983. Springer.

[38] M. Vakilian et al. Inferring method effect summaries for nested heap regions. In 24th Intl. Conf. on Automated Software Engineering, 2009. to appear.