Матричные часы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Матричные часы''' – это обобщение [[Параллельное программирование: Векторные часы|вектор…»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 1: Строка 1:
 +
[[Категория: Параллельное программирование]]
 
'''Матричные часы''' – это обобщение [[Параллельное программирование: Векторные часы|векторных часов]].
 
'''Матричные часы''' – это обобщение [[Параллельное программирование: Векторные часы|векторных часов]].
  
 
В отличие от векторных часов:
 
В отличие от векторных часов:
* каждый процесс хранит вектор векторов (матрицу) целых чисел
+
* Каждый процесс хранит вектор векторов (матрицу) целых чисел;
* при передаче сообщения передается вся имеющаяся матрица
+
* При передаче сообщения передается вся имеющаяся матрица;
* при приеме сообщения производится update собственной матрицы путем выбора покомпонентного максимума для каждого элемента. После этого, каждый элемент собственного вектора в матрице, понятным образом, составляется из максимума по соотвествующим элементам других векторов.
+
* В случае любого события, i-ый поток увеличивает на единицу свою компоненту матрицы, т.е M[i][i];
 +
* При приеме сообщения для всех строк, кроме строки, соответствующей номеру получившего потока (myId), берется покомпонентный максимум. А для M[myId][j] берется максимум из M[myId][j] и W[srcId][j], где W - матрица, которая пришла, srcId - номер потока, от которого пришла матрица W.
  
 
Используя матричные часы, мы можем оценить нижнюю границу того, что знает другой поток.
 
Используя матричные часы, мы можем оценить нижнюю границу того, что знает другой поток.
  
Кроме этого, понятным образом, обладают всеми свойствами векторных часов.
+
Кроме этого, матричные часы обладают всеми свойствами векторных часов, например, s -> t <=> s.M[s.p, x] < t.M[t.p, x] для любого х.
 
 
Иногда говорят о матричных часах, включая сюда матрицы порядка больше двух (информация типа &quot;я знаю, что x знает, что y знает&quot;), а иногда даже и порядка 1 (векторные).
 

Текущая версия на 19:06, 4 сентября 2022

Матричные часы – это обобщение векторных часов.

В отличие от векторных часов:

  • Каждый процесс хранит вектор векторов (матрицу) целых чисел;
  • При передаче сообщения передается вся имеющаяся матрица;
  • В случае любого события, i-ый поток увеличивает на единицу свою компоненту матрицы, т.е M[i][i];
  • При приеме сообщения для всех строк, кроме строки, соответствующей номеру получившего потока (myId), берется покомпонентный максимум. А для M[myId][j] берется максимум из M[myId][j] и W[srcId][j], где W - матрица, которая пришла, srcId - номер потока, от которого пришла матрица W.

Используя матричные часы, мы можем оценить нижнюю границу того, что знает другой поток.

Кроме этого, матричные часы обладают всеми свойствами векторных часов, например, s -> t <=> s.M[s.p, x] < t.M[t.p, x] для любого х.