Существует график, на котором вершины представляют фрагменты кода, а ребра - зависимости между ними.Кроме того, каждая вершина имеет два числа: сколько потоков может использовать соответствующий фрагмент кода (1, 2, ... или «столько, сколько имеется ядер»), и сколько времени, по оценкам, потребуется, если оно получитстолько потоков (по сравнению с другими - например, 1, 0,1 или 10).Идея состоит в том, чтобы запускать куски кода с учетом их зависимостей параллельно, предоставляя им такое количество потоков, чтобы общее время выполнения было наименьшим.в качестве базы?
До сих пор я думал следующим образом.Например, у нас всего 8 потоков (то есть NT = 8T) и следующий график.
+----------------+ +----------------+
+-+ A: 0.2x, 1T +----+ | F: 0.1x, 1T |
| +---+------------+ | +---+------------+
| | | |
| +---v------------+ | +---v------------+
| | B: 0.1x, 2T +-+ | | G: 0.3x, NT +-+
| +----------------+ | | +----------------+ |
| | | |
| +----------------+ | | +----------------+ |
+-> C: 0.4x, 1T | | +----> H: 0.1x, 1T | |
+--+-------------+ | +--+-------------+ |
+----+ | | |
| +----------------+ | +--v-------------+ |
| | D: 0.1x, 1T <-+ | J: 1.5x, 4T <-+
| +--+-------------+ +-------+--------+
| | |
| +--v-------------+ |
+-> E: 1.0x, 4T +------------+ |
+----------------+ | |
+--v----v--------+
+ I: 0.01x, 1T |
+----------------+
В задаче I у нас есть 2 зависимости, E и J. В качестве J-зависимостей мы имеем FG и AH.Для E, AC и ABD.Чтобы добраться до J, нам нужно 0.3x для AH и 0.4x для FG, но для этого нужно много потоков.Мы могли бы сначала запустить A и F параллельно (каждый с одним потоком).Тогда мы будем запускать G с 7 потоками и, когда A заканчивает, H с 1 потоком.Однако есть также ветвь E.В идеале, мы хотели бы, чтобы он был готов на 0,5 позже, чем J. В этом случае это довольно просто, потому что самый длинный путь к E, когда мы уже обработали A, занимает 0,4 с использованием одного потока, а другой путь занимает меньше, чем это и использует только2 потока - так что мы можем выполнить эти вычисления, когда J работает.Но если, скажем, для D потребовалось 0,6x, нам, вероятно, нужно было бы запустить его параллельно с G.
Так что я думаю, что я мог бы начать с вершины стока и сбалансировать веса подграфов, от которых это зависит,Но, учитывая эти «н-нить» задачи, не совсем понятно как.И, учитывая, что x-числа являются лишь оценками, было бы хорошо, если бы он мог внести коррективы, если бы конкретные задачи заняли больше или меньше времени, чем предполагалось.