User Tools

Site Tools


Sidebar

Master work

Thesis

Basic MPI-2

Work-Stealing with MPI-2

Implementation

Results

mestrado:ws-mpi-2

N-Queens + Hierarchical Work Stealing

  • Version: 11th August 2006
    • Two workers per node
    • Tasks exchange between different level of the managers

Pseudo Code

FIXME: Translate

if folha
	recebe tarefa
	processa
	devolve resultado
fi
else

if sou raiz
	gera tarefas
	gera lista de processadores
else
	recebe tarefas
	recebe lista de processadores
fi

if quantidade de processadores >= minimo de processadores por nó folha * ramos
	for ramos
		gera filho
		envia tarefas/ramos
		envia processadores/ramos
	while  filhos vivos > 0
		espera uma mensagem
		trata resposta do filho  (processa pedido de roubo)
		if tag-fim 
			filhos vivos --
		fi

		if !mandeiZeroTarefas[i]
			tenta pegar X tarefas da fila
			envia qtd de tarefas para o filho
			if qtd > 0
				envia novas tarefas
			else 
				mandeiZeroTarefas[i] = verdadeiro
			fi
			recebe mensagem (nao bloqueante)
		fi

		if poucas tarefas locais E !paiMandouZero
			envia resposta (soma PARCIAL e zera) para o pai (faz pedido de roubo)
			recebe qtd de tarefas (bloqueante)
	 		if qtd tarefas > 0
				recebe novas tarefas (bloqueante)
			else
				paiMandouZero = verdadeiro
		fi 
		
	end while

else // criador de folhas 
	for processadores livres
		gera folha
		envia tarefas
		recebe resposta (nao bloqueante)
	while folhasVivas > 0
		espera uma mensagem 
		trata resposta do filho (soma)
		marca processador como livre
		folhasVivas --
		tenta pegar X tarefas da fila
		if qtd > 0
			cria folha no processador livre
			folhasVivas ++
			envia qtd de tarefas para o filho
			envia tarefas
			recebe resposta (não bloqueante)			
			marca processador como ocupado
			if poucas tarefas locais E !paiMandouZero
				envia resposta (soma PARCIAL e zera) para o pai (faz pedido de roubo)	
				recebe qtd de tarefas (bloqueante)
	 			if qtd tarefas > 0
					recebe novas tarefas (bloqueante)
				else
					paiMandouZero = verdadeiro
			fi
	fim-while	
fi

if sou raiz
	imprime resultado final
else
	envia resto da soma para o pai (tag fim?)	
fi

Source Code

Results

  • Results using this implementation
mestrado/ws-mpi-2.txt · Last modified: 2007/06/20 12:41 by pagode