Параллельное динамическое программирование
CDerived::CDerived()
: CBase(...), iCount(0) //this is the initialisation list. You can initialise member variables here too. (e.g. iCount := 0)
{
//construct body
}
1 ответ
IIRC, то, что вы обычно делаете с динамическим программированием, состоит в том, чтобы рекурсивно разделить проблему на подзадачи и собрать оптимальные решения из оптимальных подрешений. Что делает его эффективным, так это то, что все оптимальные субрешения встроены в кэш, поэтому их не нужно повторно вычислять.
Если проблему можно разделить на несколько способов, вы можете разветвить решатель для каждого субрешения. Если каждая (под) проблема в среднем составляет 1 + эпсилон (что интересно, больше нуля) возможных подрешений, то таким образом вы получите много параллелизма. Вам, вероятно, понадобится блокировка записей кэша, чтобы защитить отдельные решения от создания более одного раза.
Вам нужен язык, на котором вы сможете создавать подзадачи дешевле, чем работа по их решению, и который будет счастлив, если у вас есть сразу много разветвленных задач. Типичные параллельные предложения на большинстве языков делают это плохо; у вас не может быть много разветвленных задач в системах, которые используют «модель большого стека» (см. Как работает язык без стека? ).
Мы внедрили наш язык параллельного программирования, PARLANSE, чтобы получить язык с нужными свойствами.