Un Pipeline para Resolver el Problema de la Mochila 0-1

El problema de la mochila 0-1 se enuncia asi:

Se tiene una mochila de de capacidad $C$ y $N$ objetos de pesos $w_k$ y beneficios $p_k$ . Se trata de encontrar la combinación óptima de objetos que caben en la mochila y producen el máximo beneficio.

Denotemos por $f_{k,c}$ el valor óptimo de la solución para el subproblema considerando los objetos $\{1, \ldots k\}$ y capacidad $c$ . El problema consiste en encontrar el valor de $f_{N,C}$ . Se cumple la siguiente fórmula:

$$f_{k,c} = \max \{ f_{k-1,c}, f_{k-1,c-w_k}+p_k \} \mbox{ si $c > w_k$}$$ (12.1)

y $f_{\emptyset, c} = 0$ en otro caso.

Esta fórmula nos dice que la solución para el problema $f_{k,c}$ con objetos $\{1, \ldots k\}$ puede obtenerse a partir de las soluciones de los dos subproblemas de mochila con objetos $\{1, \ldots k-1\}$ que resultan de tomar las decisiones de incluir o no el objeto $k$ .

En esta sección presentamos un programa que usa $N$ threads dispuestas en pipeline para resolver el problema.

El Fichero de Entrada

El problema se describe mediante un fichero como el que sigue:

lhp@nereida:~/Lperl/src/threads$ cat knap.dat
8
102
2
15
20
100
20
90
30
60
40
40
30
15
60
10
10
1
N=8, M = 102
weight 0
profit 0
...
N=8, M = 102
weight 0
profit 0
...
Example 2.1 pag 20 Martello and Toth
sol 280

Al ejecutar el programa se muestra la solución:

lhp@nereida:~/Lperl/src/threads$ pipeknap2.pl knap.dat
sol = 280
lhp@nereida:~/Lperl/src/threads$

El Programa Principal

El programa principal se limita a cargar las librerías y crear el pipeline de threads:

lhp@nereida:~/Lperl/src/threads$ cat -n pipeknap2.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3  use threads;
 4  use Thread::Queue;
 5  use threads::shared;
 6  use Carp;
 7  use IO::File;
 8
 9  ### main
10  my ($M, $w, $p) = ReadKnap($ARGV[0]);
11  my $N = @$w;
12
13  &pipe($N, \&knap, $M, $w, $p);

El primer argumento $N de pipe es el número de threads, el segundo la subrutina a ejecutar por la thread. En este caso una referencia a la subrutina knap. Los restantes argumentos son argumentos pasados a la subrutina que ejecuta la thread. En este caso:

• $M es la capacidad de la mochila
• $w es una referencia a la lista de pesos
• $p es una referencia a la lista de beneficios (profits)

Lectura del Problema

La subrutina auxiliar ReadKnap lee un fichero conteniendo una descripción del problema de la mochila:

79  sub ReadKnap {
80    my $filename = shift;
81
82    my $file = IO::File->new("< $filename");
83    croak "Can't open $filename" unless defined($file);
84    my (@w, @p);
85
86    my $N = <$file>;
87    my $M = <$file>;
88    for (0..$N-1) {
89      $w[$_] = <$file>;
90      $p[$_] = <$file>;
91    }
92    return ($M, \@w, \@p);
93  }

La Tarea Realizada por Cada Hilo

Los tres primeros argumentos son:

• El nombre de la tarea $k. Coincide con el índice del objeto del que se encarga la tarea. Por tanto esta tarea $k se encarga de computar los valores óptimos $f_{k,c}$ para todo $c$ los cuales son almacenados en la lista privada @f

• El canal de entrada $from_left que le comunica con el hilo encargado del cómputo de $f_{k-1,c}$ para todo $c$

• El canal de salida $to_right que le comunica con el hilo encargado del cómputo de $f_{k+1,c}$ para todo $c$

• Los argumentos relativos al problema de la mochila: la capacidad $M, la lista de pesos @w y la lista de beneficios @p

40  sub knap {
41    my $k = shift();
42    my $from_left = shift();
43    my $to_right = shift();
44    ##############
45    my $M = shift();
46    my @w = @{shift()};
47    my @p = @{shift()};
48
49    my $N = @w;
50    my @f;
51    my @left;
52
53    croak "Profits and Weights don't have the same size"
54                        unless scalar(@w) == scalar(@p);
55
56    for my $c (0..$M) {
57      $f[$c] = ($w[$k] <= $c)? $p[$k] : 0;
58    }

Antes de empezar el cómputo se inicia la lista @f (i.e. $f_{k,c}$ para todo $c$ , líneas 56-58). Si el objeto $k cabe en una mochila de capacidad $c se pondrá. En otro caso el valor inicial es cero.

La Tarea de Cada Hilo

En general, en todo pipeline hay que distinguir tres casos:

• Si se trata de la primera thread (líneas 73-75) la tarea consiste en alimentar el pipeline con los valores iniciales
• Si se trata de una tarea genérica, se recibe el valor de la izquierda - en este caso $f_{k-1,c}$ -, se actualiza el valor - en el ejemplo $f_{k,c}$ , que en el código se corresponde con $f[$c] - que depende del mismo y se envía al vecino derecho (línea 70) para que este haga lo mismo. Este envío puede eliminarse si se trata de la última thread
• La última thread contiene la solución al problema (línea 76, en nuestro caso la solución está guardada en la entrada $f[$M])

60    if ($k) {
61      for my $c (0..$M) {
62        $left[$c] = $from_left->dequeue();
63        if ($c >= $w[$k]) {
64          my $y = $left[$c-$w[$k]]+$p[$k];
65          $f[$c] = ($left[$c] < $y)? $y : $left[$c];
66        }
67        else {
68          $f[$c] = $left[$c];
69        }
70        $to_right->enqueue($f[$c]);
71      }
72    }
73    else { # thread virtual 0
74      $to_right->enqueue(@f);
75    }
76    print "sol = $f[-1]\n" if $k == ($N-1);
77  }

La Construcción del Pipeline

• En las líneas 27-29 se crean $N+1 canales. El canal $channel[$id+1] comunica la thread $id con la thread $id+1.
• En las líneas 31-33 se crean $N hilos con nombres entre 0 y $N-1. Además de los argumentos específicos de la tarea se le envían
  1. La referencia a la tarea
  2. El identificador lógico
  3. Los canales de comunicación con sus vecinos izquierdo y derecho
• Por último sincronizamos cada una de las tareas (líneas 35-37).

17  sub pipe { # crea el pipe de tamaño N
18    my $N = shift(); # número de procesadores virtuales
19    my $task = shift(); # subrutina a ejecutar
20    my @channel : shared; # array de colas
21    my @t; # array de tareas
22    # El resto de argumentos son argumentos de $task
23
24    my $id; # identificador de procesador físico
25
26    # creamos canales ...
27    for($id=0; $id <= $N; $id++) {
28      $channel[$id] = new Thread::Queue; # canal comunicando hilos $id-1 e $id
29    }
30    # creamos threads ...
31    for($id=0; $id < $N; $id++) {
32      $t[$id] = threads->new($task, $id, $channel[$id], $channel[$id+1], @_);
33    }
34    # La thread 0 no trabaja, sólo espera  ...
35    for($id=0; $id < $N; $id++) {
36      $t[$id]->join(); # join debe ser ejecutado por el padre
37    }
38  }

Ficheros Auxiliares de Entrada

Puede obtener ficheros de entrada para el ejemplo en esta sección descargando el fichero knap_dat.tgz. en la página de estos apuntes.