Все потоки
Поиск
Написать публикацию
Обновить

Комментарии 34

Досмотрел анимацию с кружочками в начале поста до конца.
Рейтинг скрыт
Попробуйте ещё и статью прочесть.
Рейтинг скрыт
А у AMD ничего такого в процессорах нет?
Рейтинг скрыт
Официально ничего объявлено не было. Есть несколько статей про AMD ASF (Advanced Synchronization Facility) — черновик расширения ISA и описаний его работы на симуляторах:

1. developer.amd.com/community/blog/just-released-advanced-synchronization-facility-asf-specification/
2. Implementing AMD's Advanced Synchronization Facility in an out-of-order x86 core / Stephan Diestelhorst, Martin Pohlack, Michael Hohmuth et al. // 5th ACMSIGPLAN Workshop on Transactional Computing. 2010. 8 p. URL: www.amd64.org/fileadmin/user_upload/pub/transact10-asfooo.pdf
3. Chung Jaewoong, Diestelhorst Stephan, Pohlack Martin et al. ASF: AMD64 Extension for Lock-free Data Structures and Transactional Memory. 2010.

Если кратко, то вот что было задумано.
1. Новые инструкции: SPECULATE, COMMIT, ABORT для старта, завершения и явной отмены транзакции, и RELEASE — оптимизирующий hint для ASF, разрешающий больше не проверять конфликты для определённого региона.
2. Внутри транзакции новый смысл придаётся инструкциям LOCK MOV — она используется для чтения и записи в память. Обычные доступы в память происходят в обход системы HTM, допустимы в транзакциях и могут быть использованы для уменьшения нагрузки на аппаратуру, управляющую точками сохранения.
3. Для сообщения причины отмены транзакции код причины сохраняется в регистре RAX.
4. На транзакцию не влияют такие события, как неправильное предсказание перехода, промах TLB и ближние вызовы функций.
5. Предоставление гарантированного успешного завершения транзакции, если она в процессе своей работы использует не более четырёх линий кэш-памяти. Т.е. достаточно малые спекулятивные регионы могут использоваться без необходимости написания fallback-ветви.
Рейтинг скрыт
Скажите пожалуйста, а как в принципе можно гарантировать пункт номер 5? Ведь это от процессора не зависит. Или они умудряются как-то контролировать работу конвейера альтернативных ветвей исполнения, чтобы текущая ветвь завершилась удачно? Уж больно сомнительно выглядит.

Или речь идет только о том что начатая операция COMMIT завершится удачно без дополнительной вероятности отказа даже в случае того что данные не были конкурентно изменены.
Рейтинг скрыт
Скажите пожалуйста, а как в принципе можно гарантировать пункт номер 5

Этот пункт гарантировать можно. Более того, в IBM System z так и сделано — один из видов транзакций (constrained transaction) гарантирует успешное завершение. Однако для этого на регион кода накладывают множество ограничений [1]:
— максимум 32 инструкции длиной,
— все инструкции должны уместиться в последовательных 256 байтах в памяти,
— если внутри есть инструкции перехода, то они должны указывать только вперёд (т.е. не должно быть циклов),
— нет вызовов процеду,
— работа идёт максимум с четырьмя выровненными секциями по 32 байта памяти,
— транзакция не содержит «сложных» инструкций (напр. FPU).
Т.е. простые типовые операции типа добавления элемента в список можно оформить как constrained transaction.

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

В Intel RTM таких гарантий, например, нет. Поэтому приходится писать код, в котором после нескольких неудачных попыток выполнить XBEGIN-XEND захватывается обычный lock, и нужная секция исполняется нетранзакционно. Пример, почему это нужно (сам на практике натыкался) — отсутствие страницы (Page Fault) при обращении внутри транзакции не вызывает обработчик ОС, который бы эту страницу подкачал с диска, а откатывает исполнение и состояние на начало, и всё заново, и опять тот же промах. Единственное «обычное» исполнение разблокирует нам транзакционный путь (страница будет подкачана), но его надо предусмотреть.

[1] Christian Jacobi, Timothy Slegel, Dan Greiner. Transactional Memory Architecture and Implementation for IBM System z. 2012 IEEE/ACM 45th Annual International Symposium on Microarchitecture www.christianjacobi.de/publications/jsg12_tx.pdf
Рейтинг скрыт
Спасибо за столь развернутый комментарий, очень интересно!
Рейтинг скрыт
Эх, вы меня опередили, хотел примерно такой же пост про транзакционную память забабахать :-). Ваше описание ТМ мне очень понарвилось!
Рейтинг скрыт
НЛО прилетело и опубликовало эту надпись здесь
Сильно не интересовался этим, но знаю что в Boost идет разработка Boost.AFIO (Async file i/o library for Boost) и там используется TSX.
Рейтинг скрыт
Точно знаю, что GCC (libitm) поддерживает интринсики и использует FASTPATH для процессоров, поддерживающих Intel TSX и Power8 (о Power8 есть ещё в Release Changes 4.9). Словом, пока только C/C++, я не слышал чтобы HTM использовали в других языках.

Насчёт производительности — есть много исследований, где изучался этот вопрос. По Intel у них на сайте сгруппировано удобно: Web Resources about Intel® Transactional Synchronization Extensions, в посте есть эта ссылка. В частности в свежем исследовании 2014 об отменах транзакций есть: Performance Evaluation of Intel® Transactional Synchronization Extensions for High-Performance Computing.

Есть ещё у меня репозиторий, где собираю ссылки на работы. Давненько не обновлял правда, нужно заняться.
Рейтинг скрыт
Есть ещё у меня репозиторий, где собираю ссылки на работы

Вот ещё списочек работ по HTM, вроде не все у Вас есть (напр. по тому же AMD ASF).
У меня есть и ещё один списочек по более общей области TM (я за ней слежу с 2007 года), если интересно, откопаю.

Да-да, помимо пачки отличных программных продуктов (OpenSolaris, MySQL, OpenOffice) Oracle забросила и перспективную аппаратную технологию

Технология аппаратной транзакционной памяти может быть и перспективная, а вот ROCK у Sun, если верить описаниям, действительно выходил монструозным и не совсем соответствующим рынку, тем более рынку, на котором работает Oracle. Легче было отменить проект, чем пытаться вытащить его, да ещё делать это одновременно с процессом интеграции одной компании в другую.
Рейтинг скрыт
Могу еще предложить статью с реализацией транзакционной памяти на Smalltalk.
Рейтинг скрыт
Спасибо. Встречал презентацию на ту же тему на slideshare, интересно.
Рейтинг скрыт
Glibc для Linux относительно свежая должна использовать Intel RTM (если железо поддерживает) для обеспечения некоторых атомарных операций из стандарта POSIX-thread. Возможно, это не включено по умолчанию; я работал с версиями, которые требовали установку переменной окружения перед запуском приложений.
Рейтинг скрыт
Почему я проголосовал «нет» на перспективу:
— Хорошая идея — всегда видеть консистентное состояние на начало транзакции. Но этого недостаточно. Изначальная идея транзакций — чтобы параллельные вычисления выполнялись с точностью так, как бы они выполнялись последовательно, допуская единичные коллизии. MVCC такого не гарантирует — требуются блокировки (на чтение).
— Архитектура большинства систем предполагает хранение состояния в persistence storage, а оперативная память используется лишь как временная внутри одной операции. Storage уже имеет все средства транзакций, плюс ряд преимуществ как масштабируемость, отказоустойчивость, etc… Для хранения состояния в памяти есть также куча in-memory storage.

Для полноты картины реализации STM на Java:
multiverse.codehaus.org/overview.html
sites.google.com/site/deucestm/
Рейтинг скрыт
TM — это альтернатива locked/lockfree алгоритмам, скажем для очереди заданий. когда несколько ядер интенсивно работают с одной структурой данных, TM позволяет уменьшить накладные расходы на синхронизацию. и алгоритмы с использованием транзакций писать проще
Рейтинг скрыт
и алгоритмы с использованием транзакций писать проще

Ещё пока сложно сказать, насколько проще — не хватает массива опытных данных. Однако есть исследования, подтверждающие это.

Я могу сказать, что транзакции имеют одно преимущество при разработке перед классическими локами — это композиционность. Т.е. если мы одну транзакцию заворачиваем в другую (например, внутренняя пришла из библиотечной функции), то у нас всё продолжает работать согласно ожиданиям. Если же внутри одной критической секции мы пытаемся зайти ещё в одну, захватив ещё один lock, то можно оказаться в ситуации дедлока.
Рейтинг скрыт
Статья мало понятная, больше похоже на обзор для тех кто уже в теме. Я весьма с трудом понял о чем речь и почти непонял профита, или случаем когда и как это можно использовать.
Из примера на с++, построение гистограммы, если я правильно понял происходит «защита» доступа к массиву histogram. Так вот вопросы:
1. Не понял зачем весь цикл выполняется в __transaction_atomic. Ведь получается что транзакцией выступает конечный результат всего цикла, а если это и есть основное действие выполняемое каждым из потоков, то как это вяжется с тем что транзакция будет отменена в случае если кто то другой уже успел изменить данные?
2. Или же расчитывается на свойство комутативности операции ++, и типо в конце все транзакции будут применены по очереди? Это означает что результаты всех транзакйций должны быть сложены вместе. А почему не вычтены или замещены?
3. А если мы всетаки делает не комутативные операции, или же они комутативны но с ограничениями? Работа с unsigned типом и операциями "-". Работа одного потока горантирует что тип не будет переполнен. Но если применять операции сразу из несколььких потоков в произвольном порядке то мы получим переполнение.
Рейтинг скрыт
Хорошие вопросы, вы здорово разобрались.
Общую информацию я поместил в начало, чтобы было более-менее понятно, как работает технология. Видимо, неудачно описал. Буду благодарен рекомендации, что поправить.
Когда и как использовать технологию рекомендации вырабатываются. Можно сказать что в некоторых областях параллельного/многопоточного программирования технология будет полезной. Есть исследования по транзакционализации существующего кода, кое-кто даже для интереса в ядре Linux перевёл подсистему FUSE на использование транзакций. В библиотеке GLIBC «под капотом» уже используются транзакции, если их поддерживает аппаратное обеспечение.
pthread_mutex_lock
# define LLL_MUTEX_LOCK_ELISION(mutex) \
  lll_lock_elision ((mutex)->__data.__lock, (mutex)->__data.__elision, \
		   PTHREAD_MUTEX_PSHARED (mutex))

int
__pthread_mutex_lock (mutex)
     pthread_mutex_t *mutex;
{
 /* code */

return LLL_MUTEX_LOCK_ELISION (mutex);

 /* code */

  return 0;
}


Где lll_lock_elision (lowlevellock.h):
#define lll_lock_elision(futex, adapt_count, private) \
  __lll_lock_elision (&(futex), &(adapt_count), private)


А __lll_lock_elision в свою очередь (elision-lock.c):
/* Adaptive lock using transactions.
   By default the lock region is run as a transaction, and when it
   aborts or the lock is busy the lock adapts itself.  */
int
__lll_lock_elision (int *futex, short *adapt_count, EXTRAARG int private)
{
  if (*adapt_count <= 0)
    {
      unsigned status;
      int try_xbegin;

      for (try_xbegin = aconf.retry_try_xbegin;
	   try_xbegin > 0;
	   try_xbegin--)
	{
	  if ((status = _xbegin()) == _XBEGIN_STARTED)
	    {
	      if (*futex == 0)
		return 0;

	      /* Lock was busy.  Fall back to normal locking.
		 Could also _xend here but xabort with 0xff code
		 is more visible in the profiler.  */
	      _xabort (_ABORT_LOCK_BUSY);
	    }

	  if (!(status & _XABORT_RETRY))
	    {
	      if ((status & _XABORT_EXPLICIT)
			&& _XABORT_CODE (status) == _ABORT_LOCK_BUSY)
	        {
		  /* Right now we skip here.  Better would be to wait a bit
		     and retry.  This likely needs some spinning.  */
		  if (*adapt_count != aconf.skip_lock_busy)
		    *adapt_count = aconf.skip_lock_busy;
		}
	      /* Internal abort.  There is no chance for retry.
		 Use the normal locking and next time use lock.
		 Be careful to avoid writing to the lock.  */
	      else if (*adapt_count != aconf.skip_lock_internal_abort)
		*adapt_count = aconf.skip_lock_internal_abort;
	      break;
	    }
	}
    }
  else
    {
      /* Use a normal lock until the threshold counter runs out.
	 Lost updates possible.  */
      (*adapt_count)--;
    }

  /* Use a normal lock here.  */
  return LLL_LOCK ((*futex), private);
}

Насчёт примера с гистограммой: видимо, я себе плохо представляю работает __transaction_atomic в GCC. Когда я писал пример, сначала поставил блок транзакции на инкремент значения в массиве, внутри цикла. Производительность оказалась очень низкой. Потом я поместил весь цикл в транзакцию и производительность меня устроила — работает быстрее, чем код с атомарными операциями. Проверил корректность работы — всё в порядке. Сообщу вам, когда разберусь как это работает. Пока приложу дамп функции hist_updater, который GCC выдаёт по флагу -fdump-tree-tmlower:

Версия с транзакцией внутри цикла:
Скрытый текст
hist_updater (void * data)
{
  int D.4096;
  int D.4095;
  unsigned int D.4094;
  unsigned int luminance;
  struct pixel p;
  struct data * d;
  size_t i;
  void * D.4098;
  long unsigned int D.4097;
  double D.4093;
  double D.4092;
  double bY.2;
  double D.4090;
  int D.4089;
  unsigned char D.4088;
  double D.4087;
  double D.4086;
  double gY.1;
  double D.4084;
  int D.4083;
  unsigned char D.4082;
  double D.4081;
  double rY.0;
  double D.4079;
  int D.4078;
  unsigned char D.4077;
  struct pixel * D.4076;
  long unsigned int D.4075;
  struct pixel * D.4074;

  d = data;
  i = 0;
  goto <D.3999>;
  <D.3998>:
  try
    {
      D.4074 = d->pixels;
      D.4075 = i * 3;
      D.4076 = D.4074 + D.4075;
      p = *D.4076;
      D.4077 = p.red;
      D.4078 = (int) D.4077;
      D.4079 = (double) D.4078;
      rY.0 = 2.1260000000000001119104808822157792747020721435546875e-1;
      D.4081 = D.4079 * rY.0;
      D.4082 = p.green;
      D.4083 = (int) D.4082;
      D.4084 = (double) D.4083;
      gY.1 = 7.1519999999999994688693050193251110613346099853515625e-1;
      D.4086 = D.4084 * gY.1;
      D.4087 = D.4081 + D.4086;
      D.4088 = p.blue;
      D.4089 = (int) D.4088;
      D.4090 = (double) D.4089;
      bY.2 = 7.220000000000000028865798640254070051014423370361328125e-2;
      D.4092 = D.4090 * bY.2;
      D.4093 = D.4087 + D.4092;
      luminance = (unsigned int) D.4093;
      luminance = luminance + 1;
      __transaction_atomic  // SUBCODE=[ GTMA_HAVE_LOAD GTMA_HAVE_STORE ]
      try
        {
          D.4094 = luminance / 16;
          D.4095 = histogram[D.4094];
          D.4096 = D.4095 + 1;
          histogram[D.4094] = D.4096;
        }
      finally
        {
          __builtin__ITM_commitTransaction ();
        }
    }
  finally
    {
      p = {CLOBBER};
    }
  i = i + 1;
  <D.3999>:
  D.4097 = d->sz;
  if (D.4097 > i) goto <D.3998>; else goto <D.4000>;
  <D.4000>:
  free (d);
  D.4098 = 0B;
  goto <D.4099>;
  <D.4099>:
  return D.4098;
}


Версия с циклом внутри транзакции:
Скрытый текст
hist_updater (void * data)
{
  unsigned int luminance;
  struct pixel p;
  long unsigned int D.4097;
  int D.4096;
  int D.4095;
  unsigned int D.4094;
  double D.4093;
  double D.4092;
  double bY.2;
  double D.4090;
  int D.4089;
  unsigned char D.4088;
  double D.4087;
  double D.4086;
  double gY.1;
  double D.4084;
  int D.4083;
  unsigned char D.4082;
  double D.4081;
  double rY.0;
  double D.4079;
  int D.4078;
  unsigned char D.4077;
  struct pixel * D.4076;
  long unsigned int D.4075;
  struct pixel * D.4074;
  struct data * d;
  size_t i;
  void * D.4098;

  d = data;
  __transaction_atomic  // SUBCODE=[ GTMA_HAVE_LOAD GTMA_HAVE_STORE ]
  try
    {
      i = 0;
      goto <D.3999>;
      <D.3998>:
      try
        {
          D.4074 = d->pixels;
          D.4075 = i * 3;
          D.4076 = D.4074 + D.4075;
          p = *D.4076;
          D.4077 = p.red;
          D.4078 = (int) D.4077;
          D.4079 = (double) D.4078;
          rY.0 = 2.1260000000000001119104808822157792747020721435546875e-1;
          D.4081 = D.4079 * rY.0;
          D.4082 = p.green;
          D.4083 = (int) D.4082;
          D.4084 = (double) D.4083;
          gY.1 = 7.1519999999999994688693050193251110613346099853515625e-1;
          D.4086 = D.4084 * gY.1;
          D.4087 = D.4081 + D.4086;
          D.4088 = p.blue;
          D.4089 = (int) D.4088;
          D.4090 = (double) D.4089;
          bY.2 = 7.220000000000000028865798640254070051014423370361328125e-2;
          D.4092 = D.4090 * bY.2;
          D.4093 = D.4087 + D.4092;
          luminance = (unsigned int) D.4093;
          luminance = luminance + 1;
          D.4094 = luminance / 16;
          D.4095 = histogram[D.4094];
          D.4096 = D.4095 + 1;
          histogram[D.4094] = D.4096;
        }
      finally
        {
          p = {CLOBBER};
        }
      i = i + 1;
      <D.3999>:
      D.4097 = d->sz;
      if (D.4097 > i) goto <D.3998>; else goto <D.4000>;
      <D.4000>:
    }
  finally
    {
      __builtin__ITM_commitTransaction ();
    }
  free (d);
  D.4098 = 0B;
  goto <D.4099>;
  <D.4099>:
  return D.4098;
}


Рейтинг скрыт
плохо оно может работать из-за того что изменения в одной строке памяти (64 байта) из разных ядер — очень медленная операция. так что тут важно что с блокировками будет ещё хуже (да и то не факт)
Рейтинг скрыт
У меня так получалось:
Скрытый текст

Тот же график без одной ветви:

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

Было бы интерестно посмотреть пример работы с ассоциативным контейнером в многопоточсное среде. Несовсем понятно должнали реализацию оного быть выполнена в транзакционном стиле.
Рейтинг скрыт
кстати, а эти графики, в случае если цикл находить в транзакции? Вопрос в том находился ли цикл под мютексом в аналогичном примере, если нет, но это неправильный тест.
Рейтинг скрыт
Думаю стоит сравнить сколько времени заимает захват мютекса с поддержкой транзакций и без. Это сильно бы прояснило перспективность подхода. Притом в двух случаях, конкурентный захват и нет.
Рейтинг скрыт
Хм, а как HLE обеспечивает откат транзакционных операций?
То есть пусть всем потокам сказано что лока нет, они проделали какую-то работу с разными непересекаюшимися участками памяти.
Затем происходит модификация общих данных, и один из потоков продолжает выполнение, а что происходит с остальными?
Рейтинг скрыт
А остальные откатываются на начало, если были конфликты. И повторяют вход в критическую секцию, или элизионно, или классически с атомарной инструкцией. Детали зависят от реализации.
В классической схеме им бы просто не дали войти в критическую секцию, и все потоки, кроме одного, консервативно сидели на начале критической секции и по одиночке её проходили, даже если конфликт возникает крайне редко.

Чтобы работал откат, во внутреннем буфере сохраняются состояния всех регистров перед входом в транзакцию. Есть и другие механизмы, например, вести лог изменений.
Рейтинг скрыт
Понятно что можно много чего сделать, но используется ли это в текущем железе, вот в чем вопрос.
В принципе проверить-то не сложно, только Haswell'a под рукой нет.
Кроме регистров можно изменить еще много чего.
Рейтинг скрыт
> В принципе проверить-то не сложно, только Haswell'a под рукой нет.
Проверить так легко не получится, т.к. внутри транзакции нельзя остановиться дебаггером — такая попытка вызовет её откат.

> Кроме регистров можно изменить еще много чего.
Вообще рекомендую посмотреть спецификации, они многое объяснят — что можно делать внутри HLE-региона, а что нет. Например, x87 FPU, MSR, CR0-CR8, LDTR, GDTR и т.д. трогать нельзя — это вызовет откат. Свойство атомарности не зря придумано для транзакций.
Рейтинг скрыт
Какие-то чуваки перевели статью и запостили на англоязычный аналог хабра без указания оригинала. Понятное дело, смысл терялся при прямом и обратном переводе. Балбесы =)
Рейтинг скрыт
Интересно, тут вот говорят что STM хотели включить в .NET 4 (во всяком случае выпустили особую версию с ним). Неужто заглохло?
Рейтинг скрыт
Возможно ли использовать трензакционную память не совсем по назначению?
Например, решая переборную задачу, начинать транзакцию на каждый вариант и прерывать их, если в другой транзакции вариант оказался лучше?
Рейтинг скрыт
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr