Este artigo foi traduzido por máquina.

.imgright1 { margin: 5px 0px 10px 10px; width:353px; font-weight: normal; font-size: 14px; color: #003399; font-family: "Segoe UI", Arial; }

Assuntos .NET

Operações com dependências de paralelismo

Stephen Toub

P Eu tenho um sistema onde vários componentes precisam ser executado, mas esses componentes podem possuir dependências entre si. Gostaria de poder executar esses componentes em paralelo sempre que possível. Como pode fazer isso?

A este é um problema muito comum no desenvolvimento de software, serial ou paralela. Em uma implementação seqüencial, uma abordagem comum é modelar as dependências como um gráfico. Cada componente é representado por um nó no gráfico, e cada dependência é representada por uma borda direcionada entre os dois nós compartilhamento a dependência. Isso cria o que é conhecido como um directed Acíclico gráfico (DAG), assumindo que não há nenhum ciclos (por exemplo, 1 componente depende componente 2, que depende do componente 3, que depende volta componente 1). Uma classificação topológico, em seguida, pode ser usada para criar uma ordem parcial entre esses componentes para que, se você executar os componentes em seqüência em que ordem, todas as dependências de um componente será concluiu pelo tempo esse componente é executado.

fig01.gif

Figura 1 gráfico Acíclico um directed

Vamos dizer que você tem componentes 8, com as seguintes dependências (que irá consultar este exemplo nesta coluna):

  • Componentes 1, 2 e 3 dependem nada mais
  • Componente 4 depende do componente 1
  • Componente 5 depende componentes 1, 2 e 3
  • Componente 6 depende componentes 3 e 4
  • Componente 7 depende componentes 5 e 6
  • Componente 8 depende do componente 5

Um DAG para este conjunto de dependências é mostrado na Figura 1 . Em um aplicativo seqüencial, executando uma classificação topológico sobre este gráfico, você pode surgir com um dos vários orderings parciais, incluindo apenas executá-los em ordem (1,2,3,4,5,6,7,8), que por acaso, satisfazer as dependências descritas aqui crescente. Outros orderings claro são possíveis, como 3,2,1,5,8,4,6,7.

A capacidade de executar em paralelo alguns dos componentes em um gráfico como esse poderia produzir valiosos aumentos de velocidade. Imagine, apenas por questão de ilustração, que cada componente usa um segundo para executar, que cada componente é seqüencial em natureza, que o aplicativo está sendo executado em uma máquina com um número infinito de núcleos de processamento, e que não há nenhum processamento necessário para algo diferente de executar os componentes (sobrecarga). Se você fosse executar todos os componentes em seqüência, levaria oito segundos. Mas você pode fazer melhor em paralelo. Você pode executar componentes 1, 2 e 3 simultaneamente, fazendo um total de um segundo. Você pode, em seguida, executar 4 e 5 simultaneamente, fazendo outro segundo. Quando os estiverem concluídos, você pode executar 6 e 8 simultaneamente, fazendo outro segundo. E Finalmente você pode executar 7, para um total geral de quatro segundos. Usando paralelismo, você já reduzir tempo em execução o problema de exemplo, portanto, na metade.

Como mencionado, este tipo de problema aparece em vários domínios com problemas software diferente. Considere, por exemplo, MSBuild. Microsoft .NET Framework–based projetos com freqüência referenciar outros projetos de .NET na mesma solução, assim, configurar uma dependência entre os dois projetos. Para o .NET Framework 3.5, MSBuild iniciado oferecendo a opção /m, que utiliza os processadores disponíveis na máquina para colocar em paralelo o processo de compilação, utilizando as informações de dependência como as referências de projeto que acabei de mencionar.

No restante desta coluna, será criar uma classe de DependencyManagement pequena para ajudar a resolver esses problemas. Eis uma estrutura de tópicos da API pública:

public class DependencyManager 
{
  public void AddOperation(
    int id, Action operation, params int [] dependencies);
  public event EventHandler<OperationCompletedEventArgs> 
    OperationCompleted;
  public void Execute();
}

O ponto de entrada principal no tipo é o método de AddOperation, que aceita uma identificação exclusiva que você fornecer para representar uma operação, o delegado a ser executada para essa operação, e um conjunto de dependências na cujo conclusão esta operação se baseia. Se uma operação não tem dependências, a matriz de parâmetro irá estar vazia.

O evento OperationCompleted é disparado sempre que uma das operações constituintes conclusão, fornecendo a identificação da operação bem como inicial e final horas de sua execução.

E por fim, o método Execute é acionada desativar o processo e aguarda a todas as operações para concluir. Enquanto a classe DependencyManager será executado operações em paralelo, a API propriamente dito não deve ser thread-safe, que significa que apenas um thread deve ser usado para acessar AddOperation e executar uma vez.

Esta classe permite-me para expressar o problema do exemplo anterior da seguinte maneira:

Action oneSecond = () => { ComputeForOneSecond(); };
DependencyManager dm = new DependencyManager();
dm.AddOperation(1, oneSecond);
dm.AddOperation(2, oneSecond);
dm.AddOperation(3, oneSecond);
dm.AddOperation(4, oneSecond, 1);
dm.AddOperation(5, oneSecond, 1, 2, 3);
dm.AddOperation(6, oneSecond, 3, 4);
dm.AddOperation(7, oneSecond, 5, 6);
dm.AddOperation(8, oneSecond, 5);
dm.Execute();

Internamente, informações sobre cada operação registrada são armazenadas em uma classe OperationData:

private class OperationData {
  internal int Id;
  internal Action Operation;
  internal int [] Dependencies;
  internal ExecutionContext Context;
  internal int NumRemainingDependencies;
  internal DateTimeOffset Start, End;
}

Os campos de ID, operação e dependências armazenam os dados correspondentes passados para o método AddOperation como parâmetros e o campo de contexto armazena o ExecutionContext capturado no momento AddOperation foi chamado (para obter mais informações sobre por que isso é importante, consulte minhas últimos algumas colunas de .NET Matters). Além disso, OperationData armazena o número de dependências restantes que precisam ser concluídas antes que ele possa executar. Finalmente, ele mantém registro do início e hora final para esta operação e esses será relatada com um consumidor de DependencyManager quando o evento OperationCompleted é gerado para esta operação específica.

Duas coleções são usadas para manter o conjunto de operações adicionado à instância do DependencyManager:

private Dictionary<int, OperationData> _operations  =
  new Dictionary<int, OperationData>();private Dictionary<int, List<int>> _dependenciesFromTo;

O primeiro dicionário contém uma entrada para cada operação adicional e mapeia o ID de uma operação para sua instância OperationData; isso torna rápido e fácil consultar os dados para uma operação dada sua identificação. Enquanto que primeiro dicionário conter todas as informações que você precisa fazer seu trabalho, ele não contém essa informação em um formato que faz o trabalho fácil ou eficiente. O dicionário último corrige isso fornecendo um mapeamento da identificação de uma operação para todas as identificações de operações que dependem diretamente dele. Por exemplo, no problema do exemplo mostrado anteriormente, a entrada de ID 1 nesse dicionário poderia mapear para uma lista contendo IDs 4 e 5, desde que as duas operações dependem diretamente ID 1 concluir. Esse dicionário torna rápido e fácil para uma operação Concluindo enviar uma notificação de conclusão para todas as outras operações que dependem dele.

A classe DependencyManager contém três campos mais particulares, bem como os dicionários:

private object _stateLock = new object();
private ManualResetEvent _doneEvent;
private int _remainingCount;

O campo _stateLock é usado durante a execução assíncrona das operações registradas para proteger o estado compartilhado acessado pelo processamento dessas operações, como dicionários e os dados que eles contêm. O ManualResetEvent simplesmente é usado como um mecanismo para o método Execute para aguardar a todas as operações concluir. A última operação para concluir definirá o evento, permitindo que o método Execute sair. Uma operação sabe que é o último concluir, pois todas as operações diminui o campo _remainingCount quando eles concluída. Assim, se um diminui de operação o valor e localiza é agora zero, a operação sabe ele é o último e pode definir o _doneEvent. (Como um aparte, esse tipo de lógica de contagem regressiva é comumente encontrado em problemas de paralelismo de bifurcação/junção, e o novo CountdownEvent in the .NET Framework 4.0 torna esses problemas mais fácil de implementar.)

O código para o método AddOperation é simples.

public void AddOperation(
    int id, Action operation, params int[] dependencies) {
  if (operation == null) 
    throw new ArgumentNullException("operation");
  if (dependencies == null) 
    throw new ArgumentNullException("dependencies");

  var data = new OperationData {
    Context = ExecutionContext.Capture(),
    Id = id, Operation = operation, 
      Dependencies = dependencies
  };
  _operations.Add(id, data);
}

Depois de verificar que os argumentos são válidos, o método captura todos os dados em uma instância da classe OperationData e essa instância é armazenada no dicionário de todas as operações de controle.

Afinal de contas das operações foram adicionadas, você pode executar o método de execução, mostrado na Figura 2 , para obter o processo vai. No início do método, ele configura as informações de dependência para a execução, ou seja transpô as informações de dependência armazenadas em cada OperationData, que você pode facilmente consultar operações que têm dependência em uma operação destino dada de identificação. do destino

A Figura 2 iniciar o processo

public void Execute() {
  // TODO: verification will go here later
  // Fill dependency data structures
  _dependenciesFromTo = new Dictionary<int, List<int>>();
  foreach (var op in _operations.Values) {
    op.NumRemainingDependencies = op.Dependencies.Length;

    foreach (var from in op.Dependencies) {
      List<int> toList;
      if (!_dependenciesFromTo.TryGetValue(from, out toList)) {
        toList = new List<int>();
        _dependenciesFromTo.Add(from, toList);
      }
      toList.Add(op.Id);
    }
  }

  // Launch and wait
  _remainingCount = _operations.Count;
  using (_doneEvent = new ManualResetEvent(false)) {
    lock (_stateLock) {
      foreach (var op in _operations.Values) {
        if (op.NumRemainingDependencies == 0) 
          QueueOperation(op);
      }
    }
    _doneEvent.WaitOne();
  }
}

private void QueueOperation(OperationData data) {
  ThreadPool.UnsafeQueueUserWorkItem(state => 
    ProcessOperation((OperationData)state), data);
}

O restante do método e funciona localizando todas as operações que têm zero dependências e enfileiramento-los para execução para o .NET ThreadPool.

Anteriormente, mencionei que o método Execute e o AddOperation não são thread-safe em relação ao outro, que significa que esses métodos são deve ser chamado em seqüência, usando primeiro AddOperation para adicionar todas as operações para executar e, em seguida, chamar executar. Como resultado, observe que AddOperation acessa os dicionários sem nenhum bloqueio ou outro mecanismo de sincronização do estado compartilhado. Entretanto, executar dispor parte do seu corpo em um bloqueio. Isso ocorre porque uma vez é enfileirados o primeiro item de trabalho para ser executado, esse item de trabalho pode acessar e modificar os dicionários simultaneamente com o restante do corpo da execução. Para impedir que esses corridas ocorra, o restante do corpo da execução é protegido. Quando todo o trabalho relevante tem sido enfileirado, o método Execute bloqueia aguardando todo o trabalho para concluir.

QueueOperation simplesmente coloca o método ProcessOperation ThreadPool e ProcessOperation executa a operação especificada. Esse método é mostrado na Figura 3 . A primeira parte do método simplesmente executa o delegado armazenado no OperationData fornecido, isso sob o ExecutionContext fornecido (se um pode ser capturado) e tempo de execução, armazenar os resultados de volta na estrutura de dados para relatórios posteriores. (Para informações mais detalhadas do tempo, System.Diagnostics.Stopwatch pode ser usado em vez de DateTimeOffset.)

A Figura 3 processamento de uma operação

private void ProcessOperation(OperationData data) {
  // Time and run the operation's delegate
  data.Start = DateTimeOffset.Now;
  if (data.Context != null) {
    ExecutionContext.Run(data.Context.CreateCopy(), 
      op => ((OperationData)op).Operation(), data);
  }
  else data.Operation();
  data.End = DateTimeOffset.Now;


  // Raise the operation completed event
  OnOperationCompleted(data);

  // Signal to all that depend on this operation of its
  // completion, and potentially launch newly available
  lock (_stateLock) 
{
    List<int> toList;
    if (_dependenciesFromTo.TryGetValue(data.Id, out toList)) {
      foreach (var targetId in toList) {
        OperationData targetData = _operations[targetId];
        if (--targetData.NumRemainingDependencies == 0) 
          QueueOperation(targetData);
      }
    }
    _dependenciesFromTo.Remove(data.Id);


    if (--_remainingCount == 0) _doneEvent.Set();
  }
}

private void OnOperationCompleted(OperationData data) {
  var handler = OperationCompleted;
  if (handler != null)
    handler(this, new OperationCompletedEventArgs(
      data.Id, data.Start, data.End));
}

public class OperationCompletedEventArgs : EventArgs {
  internal OperationCompletedEventArgs(
    int id, DateTimeOffset start, DateTimeOffset end) {
    Id = id; Start = start; End = end;
  }
  public int Id { get; private set; }
  public DateTimeOffset Start { get; private set; }
  public DateTimeOffset End { get; private set; }
}

Uma vez que a operação seja concluída, você precisa notificar quaisquer operações dependentes. Eis onde o dicionário handy_dependenciesFromTo entra em cena. Você simplesmente enumerar todas as operações que dependem esse um determinado, consultar suas instâncias OperationData e diminui seus NumRemainingDependencies por um. Se seu número de dependências restantes for zero, agora está qualificadas para a execução, e QueueOperation é usado para iniciar cada operação qualificada.

Você também pode fazer um pouco housecleaning: Agora que a operação estiver concluída, você não precisará seu in_dependenciesToFrom entrada novamente, por isso, você pode removê-lo.

Finalmente, você notificar o DependencyManager que uma operação mais estiver concluída, potencialmente configuração the_doneEvent (para ativar o método Execute) se ele é a última operação.

Sem o tratamento de exceção é mostrado nesta implementação, mas adicionar alguns pode ser importante dependendo de como a classe é usada. Por exemplo, se um dos manipuladores de eventos OperationCompleted levantar uma exceção, essa exceção será propagar fora do OnOperationCompleted (que apenas gera o evento), impedindo que qualquer dependência nesta operação sejam notificados e provavelmente deslocado o sistema. Para obter uma implementação eficiente, que teria que ser abordados.

O que você viu até agora representa a maior parte da implementação. No entanto, ainda existem algumas coisas interessantes que podem ser feitas. Por exemplo, a implementação assume que todas as operações que são dependências de outras operações foram registradas quando a que execução é chamada. Se eles não estiver, as notificações relevantes de conclusão nunca serão geradas e execute nunca retornará porque algumas dependências não foram atendidas e, portanto, algumas operações já não será executado. Para resolver isso, você pode implementar um método VerifyThatAllOperationsHaveBeenRegistered que irá capturar tal uso indevido e fazer uma chamada a ele no início do método Execute:

private void VerifyThatAllOperationsHaveBeenRegistered() {
  foreach (var op in _operations.Values) {
    foreach (var dependency in op.Dependencies) {
      if (!_operations.ContainsKey(dependency)) {
        throw new InvalidOperationException(
          "Missing operation: " + dependency);
      }
    }
  }
}

Da mesma forma, você pode verificar que há na verdade não ciclos no gráfico. Se houvessem ciclos, o método Execute nunca seria concluída porque algumas dependências permaneceriam insatisfeitas. Por exemplo, imagine que você erroneamente digitar que esse componente 2 dependentes no componente 8. Isso poderia causar um ciclo (2 => 5 => 8 => 2) que impediria que componentes 2, 5, 7 e 8 em execução. Você pode detectar esses ciclos com um método VerifyThereAreNoCycles, novamente fazer uma chamada para esse método no início da execução (após VerifyThatAllOperationsHaveBeenRegistered).

Há vários algoritmos apropriados para localizar ciclos em um gráfico. Uma é fazer uma pesquisa de profundidade-primeiro no gráfico de cada nó de entrada no gráfico (no caso de neste artigo, que é uma operação que não tem dependências, como componentes 1, 2 e 3 no meu exemplo). Como você faz uma pesquisa de profundidade-primeiro, você marcar um nó quando você visita-lo. Se você visitar um nó que já foi marcado, você encontrou um ciclo.

Outra solução se baseia a classificação topológico mencionada no começo desta coluna. Se a classificação topológico falhar, o gráfico tem um ciclo. Como com uma classificação topológico também é útil em geral (por exemplo, se você quiser usar opcionalmente DependencyManager para executar seqüencialmente), escolhi dessa abordagem.

a Figura 4 mostra a implementação de um método CreateTopologicalSort, que retorna uma lista ordenada parcialmente de identificações de operação. (O código também mostra o método VerifyThereAreNoCycles, que simplesmente chama CreateTopologicalSort e lança uma exceção se o método retornou nulo, indicando que a classificação falhou.) A primeira coisa a fazer é converter o dicionário de operações em estruturas de dados de dicionário temporário para a operação de classificação. Esses dicionários temporários mapeiam em conceito para os dicionários que vimos anteriormente. Na verdade, dependenciesToFrom mapeia uma identificação de operação para as identificações de todas as operações depende (bordas de entrada). Por outro lado, dependenciesFromTo mapeia uma identificação de operação para as identificações de todas as operações que dependem dele (bordas de saída). À medida que o algoritmo é executado, você lentamente será Compare para baixo o conteúdo desses dicionários até, Felizmente, não há nada para a esquerda.

Figura 4 classificação topológico e ciclo de detecção

private void VerifyThereAreNoCycles() {
  if (CreateTopologicalSort() == null) 
    throw new InvalidOperationException("Cycle detected");
}

private List<int> CreateTopologicalSort() {
  // Build up the dependencies graph
  var dependenciesToFrom = new Dictionary<int, List<int>>();
  var dependenciesFromTo = new Dictionary<int, List<int>>();
  foreach (var op in _operations.Values) {
    // Note that op.Id depends on each of op.Dependencies
    dependenciesToFrom.Add(op.Id, new List<int>(op.Dependencies));

    // Note that each of op.Dependencies is relied on by op.Id
    foreach (var depId in op.Dependencies) {
      List<int> ids;
      if (!dependenciesFromTo.TryGetValue(depId, out ids)) {
        ids = new List<int>();
        dependenciesFromTo.Add(depId, ids);
      }
      ids.Add(op.Id);
    }
  }

  // Create the sorted list
  var overallPartialOrderingIds = new List<int>(dependenciesToFrom.Count);
  var thisIterationIds = new List<int>(dependenciesToFrom.Count);
  while (dependenciesToFrom.Count > 0) {
    thisIterationIds.Clear();
    foreach (var item in dependenciesToFrom) {
      // If an item has zero input operations, remove it.
      if (item.Value.Count == 0) {
        thisIterationIds.Add(item.Key);

        // Remove all outbound edges
        List<int> depIds;
        if (dependenciesFromTo.TryGetValue(item.Key, out depIds)) {
          foreach (var depId in depIds) 
{
            dependenciesToFrom[depId].Remove(item.Key);
          }
        }
      }
    }

    // If nothing was found to remove, there's no valid sort.
    if (thisIterationIds.Count == 0) return null;

    // Remove the found items from the dictionary and 
    // add them to the overall ordering
    foreach (var id in thisIterationIds) dependenciesToFrom.Remove(id);
    overallPartialOrderingIds.AddRange(thisIterationIds);
  }

  return overallPartialOrderingIds;
}

Depois que os dicionários são preenchidos, você iniciar a execução o algoritmo. A idéia é que você cull do gráfico todos os nós que possuem zero bordas entradas — no contexto deste artigo, que significa que operações que têm não dependências em outras operações. Quando você encontrar essas operações, você adiciona-los para o final dos resultados classificados (a ordem na qual você adiciona-los para o final não importa, portanto a nomenclatura "ordem parcial"), e você removê-los do gráfico. Você também precise remover todas as bordas de saída essas operações, que você pode facilmente localizar usando o dicionário dependenciesFromTo. Você fazer esse processo diversas vezes até o gráfico contém zero nós, momento em que o algoritmo é concluído e você retornar a ordem é criada. Se, no entanto, você recebe a um ponto em que todos os nós no gráfico tenha entrada edges, o gráfico contido um ciclo, e não há nada mais que você pode fazer.

Com isso, a implementação é concluída. No início desta coluna, mostrei o código que pode ser usado com a classe DependencyManager para executar o problema de exemplo que tenha sido referência em todo. Se você irá se lembrar, eu sugerida que você pode obter o tempo de execução para baixo para quatro segundos. Na verdade, ao executar esse código de exemplo em meu laptop, recebo intervalos que passe dentro de alguns milissegundos de quatro segundos.

Isso é parcialmente sorte, no entanto. O ambiente hipotético que postulated incluído uma máquina com um número infinito de núcleos. Meu laptop, infelizmente, não está configurado como e, em vez disso, é limitado a apenas dois núcleos. No entanto, devido a ordem direita, o problema ainda poderá executar em quatro segundos com apenas duas unidades de processamento. Se operações 1 e 2 iniciar a execução, e um segundo 3 mais recente e 4 pode iniciar a execução, em seguida, uma segunda 5 posterior e 6 pode iniciar executando e um segundo posteriormente 7 e 8 pode iniciar a execução.

Mas o que acontece se operações 2 e 3 ser executado primeiro, em vez de operações 1 e 2? Isso é certamente possível, já que todas as operações 1, 2 e 3 não tem nenhuma dependência. Se operações 2 e 3 executar primeira, em seguida, nas próximas operações de iteração 1 e 5 estará disponível para ser executado. Depois que eles passarem, operações 4 e 8 poderão ir. Mas na próxima iteração, somente operação 6 estarão disponível, como operação 7 depende a conclusão da operação 6, e, portanto, o cálculo inteiro levará cerca de cinco segundos em vez de quatro.

No meu aplicativo de exemplo, quando eu alterou a ordem em que chamei AddOperation a primeira operações de registro 3 e 2, a hora de saída confirmado esse problema, com um tempo de execução de apenas em cinco segundos. Se como um desenvolvedor você tem a priori saber quanto cada operação levará, você pode usá-lo para criar uma ordem melhor de como as operações são iniciadas. Que é deixada como um exercício para você.

Claro existem muitas outras coisas interessantes que você pode criar fora nesta implementação, usá-lo como um ponto de partida. Para operações com não dependências, talvez seja conveniente os para conseguir iniciar executando logo conforme eles estiver adicionados ao DependencyManager, em vez de ter que esperar até que a execução é chamada. Você pode deseja poder executar o DependencyManager assincronamente e esperar mais tarde em seus resultados, ou fazer algo como alternativa quando sua conclusão. Convém poder criar gráficos de DependencyManagers. Convém operações para ser capaz de retornar dados que passam junto às dependências, criando, portanto, backup de fluxo de dados grandes redes. E assim por diante. Há muitas possibilidades de interessantes e útil. Aproveite!

Envie suas dúvidas e comentários para .NET Matters para netqa@microsoft.com.

Stephen Toub é uma líder de gerente de programas sênior na equipe de plataforma de computação paralela da Microsoft. Ele também é editor colaborador para MSDN Magazine.