Algoritmo di distribuzione bilanciata

Question

Sto lavorando su del codice per un cluster liberamente accoppiato. Per ottenere prestazioni ottimali durante i lavori, ho il cluster di rimappare i suoi dati ogni volta che un bambino entra o esce. Questo alla fine sarà reso facoltativo, ma per ora esegue il suo bilanciamento dei dati per impostazione predefinita. Il mio bilanciamento consiste essenzialmente nel garantire che ogni bambino non abbia mai più del numero medio di file per macchina, più uno. Quello positivo è per il resto se la divisione non è pulita. E poiché il resto sempre sarà inferiore al numero di bambini [tranne 0 caso, ma possiamo escluderlo], i bambini dopo un bilanciamento avranno al massimo avg + 1.

Tutto sembra a posto, fino a quando ho capito che il mio algoritmo è O (n!). Scorri l'elenco dei bambini, scopri avg, resto, chi ne ha troppi e chi ne ha troppo pochi. Per ogni bambino nell'elenco di troppi, vai nell'elenco, invia a ogni bambino che ne ha troppo pochi.

C'è una soluzione migliore a questo? Sento che ci deve essere.

Modifica: ecco alcuni psuedocode per mostrare come ho derivato O (n!):

foreach ( child in children ) {
    if ( child.dataLoad > avg + 1 ) {
        foreach ( child2 in children ) {
            if ( child != child2 && child2.dataLoad < avg ) {
                sendLoad(child, child2)
            }
        }
    }
}

Modifica: O (n ^ 2). Foreach n, n = > n * n = > n ^ 2. Immagino di non aver bevuto abbastanza caffè stamattina! ;)

In futuro vorrei passare a un metodo di distribuzione più flessibile e resiliente [pesi ed euristica], ma per ora funziona una distribuzione uniforme dei dati.

Answer 1

@zvrba: non è nemmeno necessario ordinare l'elenco. Quando si attraversa l'elenco per la seconda volta, spostare tutti gli elementi con un carico di lavoro medio inferiore alla fine dell'elenco (è possibile mantenere un puntatore all'ultimo elemento al primo attraversamento). L'ordine non deve essere perfetto, cambia solo quando gli iteratori devono essere aumentati o diminuiti nell'ultimo passaggio.

Vedi la risposta precedente

L'ultimo passaggio sarebbe simile a:

Nel secondo passaggio tenere un puntatore al primo elemento con un carico di lavoro inferiore alla media in child2 (per evitare la necessità di avere un doppio elenco di collegamenti).

for each child in list {
  if child2 == nil then assert("Error in logic");
  while child.workload > avg + 1 {
    sendwork(child, child2, min(avg + 1 - child2.workload, child.workload - (avg + 1)))
    if child2.workload == avg + 1 then child2 = child2.next;
  }
}

Answer 2

Penso che la tua analisi sia errata:

• scorrendo l'elenco per scoprire che la media è O (n)
• la creazione di elenchi di bambini con troppi o troppo pochi blocchi di dati è anche O (n)
• lo spostamento dei dati è proporzionale alla quantità di dati

Come sei arrivato a O (n!)?

È possibile ordinare l'elenco [O (n lg n) nel numero di figli], in modo che sul davanti ci siano figli con troppo lavoro e alla fine figli con troppo poco lavoro. Quindi attraversa l'elenco da entrambe le estremità contemporaneamente: un iteratore punta a un bambino con dati in eccesso, l'altro a un bambino con mancanza di dati. Trasferisci i dati e sposta un iteratore in avanti o l'altro all'indietro.

Answer 3

Potresti voler provare un approccio completamente diverso, come un hashing coerente.

Vedi qui per un'introduzione relativamente semplice all'argomento: http://www8.org/w8-papers/2a-webserver/ caching / paper2.html

(Esistono anche articoli più profondi, a partire da Karger et al)

Ho creato un'implementazione funzionante di hash coerente in Erlang che puoi esaminare se lo desideri:

http://distributerl.googlecode.com/svn/trunk/chash.erl

Answer 4

Il codice che hai pubblicato ha complessità O (n ^ 2). Tuttavia, è possibile farlo in tempo lineare come ha osservato Malach, dove n è il numero di elementi nell'elenco figlio.

Considera: il ciclo interno ha n iterazioni e viene eseguito al massimo n volte. n * n = n ^ 2.