NBSP: a network-bound scheduling policy for distributed parallel applications.

Este trabalho apresenta uma nova política de escalonamento para aplicações paralelas Network-Bound baseada no impacto do processamento causado pela comunicação entre processos. O modelo utilizado quantifica o volume de tráfego imposto sobre a rede de comunicação por meio dos parâmetros latência e sobrecarga. Tais parâmetros representam a carga que cada processo impõe sobre a rede e o atraso sobre a CPU devido às operações na rede. Esse atraso é representado na política por meio da métrica slowdown. Equações matemáticas são definidas para a quantificação dos custos envolvidos no processamento e na troca de mensagens, do mesmo modo, são propostas equações para determinar a largura máxima de banda (bandwidth) utilizadas nas tomadas de decisões de escalonamento. Outra característica importante da política é a definição de uma constante k, que delimita a utilização máxima permitida da rede de comunicação. O valor de k define a adoção de duas possíveis técnicas de escalonamento: escalonamento em grupo, ou por intermédio da rede de comunicação. As técnicas propostas são incorporadas à política de escalonamento DPWP (originalmente CPU-Bound) gerando uma extensão Network-Bound. Resultados experimentais e de simulação confirmam o aumento de desempenho de aplicações paralelas sob supervisão da política DPWP estendida, denominada NB SP, quando comparadas às execuções supervisionadas pela DPWP original.This work presents a new scheduling policy for Network-Bound parallel applications based on impacts of the processing operations resulting from the communication among processes. The model adopted quantifies the traffic volume imposed on the communication network by means of the latency and the overhead parameters. Such parameters represent the load that each process imposes over the network and the delay on the CPU, as a consequence of the network operations. The delay is represented on the model by mean of metric measurements slowdown. The mathematics equations that quantify the costs involved in the processing operation and message exchange are defined. In the same way, equations to determine the maximum network bandwidth are used on the decision-making scheduling. Another important feature of the policy is the definition of a constant k that delimitates the communication network maximum allowed usage. The k value defines the adoption of two possible scheduling techniques: group scheduling or through communication network. The proposed techniques are incorporated to the DPWP scheduling policy (oriniginally CPU-Bound), generating an extension Network-Bound. Experimental and simulation results confirm the performance enhancement of parallel applications under supervision of the extended DPWP policy, denominated NB SP, when compared to the executions supervised by the original DPWP