Управление параллелизмом с низкими накладными расходами


Спекулятивная схема


Сначала рассмотрим локальную спекулятивную схему, описанную в п. 4.2.1. Для спекуляции нам требуется знать время простоя процесса каждого раздела в течение выполнения многораздельной транзакции. Если время процессора, требующееся для выполнения многораздельной транзакции в одном разделе, равно tmpN, то величина сетевой задержки tmpN равняется tmp - tmpC. Поскольку мы можем совместить выполнение следующей многораздельной транзакции с периодом ожидания ответа от сети, предельное время при выполнении рабочей нагрузки из только многораздельных транзакций tmpL вычисляется как max(tmpN, tmpC), а время простоя процессора tmpI – как max(tmpN, tmpC) - tmpC.

Предположим, что для спекулятивного выполнения однораздельной транзакции требуется время tspS. За время простоя, возникающее при выполнении многораздельной транзакциии, в каждом разделе можно выполнить не более tmpI / tspS однораздельных транзакций. При выполнении в системе N × f многораздельных транзакций в каждом разделе выполняется N × (1- f) / 2 однораздельных транзакций. Следовательно, в среднем каждая многораздельная транзакция отделяется (1- f) / 2 × f однораздельными транзакциями. Поэтому для каждой многораздельной транзакции число однораздельных транзакций, которые можно спекулятивно выполнить в каждом разделе, задается следующей формулой:

Nhidden = min ((1- f) / (2 × f), tmpI / tspS)

Тем самым, время выполнения N и результирующая пропускная способность вычисляются следующим образом:

время = N × f × tmpL + (N × (1- f) - 2 × N × f × Nhidden) × (tsp / 2)

пропускная способность = 2 / (2 × f × tmpL + ((1- f) - 2 × f × Nhidden) × tsp)

В нашем конкретном случае tmpN > tmpC, и поэтому мы можем упростить формулы:

Nhidden = min ((1- f) / (2 × f), (tmp - 2 &times tmpC) / tspS)

пропускная способность = 2 / (2 × f × (tmp - tmpC) + ((1- f) - 2 × f × Nhidden) × tsp)

Разные значения функции min соответствуют двум разным поведениям системы. Если (1- f) / (2 × f) ≥ tmpI / tspS, то время простоя полностью используется. В противном случае в системе отсутствует нужное число однораздельных транзакций, чтобы можно было полностью скрыть сетевые задержки, и пропускная способность будет быстро падать после того, как значение f превзойдет tspS / (2 × tmpI + tspS).




Начало  Назад  Вперед



Книжный магазин