Матричные часы — различия между версиями
м (переименовал «Параллельное программирование: Матричные часы» в «Матричные часы») |
|||
| Строка 3: | Строка 3: | ||
В отличие от векторных часов: | В отличие от векторных часов: | ||
| − | * | + | * Каждый процесс хранит вектор векторов (матрицу) целых чисел; |
| − | * | + | * При передаче сообщения передается вся имеющаяся матрица; |
| − | * | + | * В случае любого события, 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] для любого х. |
| − | |||
| − | |||
Версия 20:19, 9 марта 2018
Матричные часы – это обобщение векторных часов.
В отличие от векторных часов:
- Каждый процесс хранит вектор векторов (матрицу) целых чисел;
- При передаче сообщения передается вся имеющаяся матрица;
- В случае любого события, 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] для любого х.
