Práctica: Prefijos de Productos de Matrices

Escriba subrutinas receiveref y sendref que extiendan las subrutinas de recepción y envío que introdujo en la práctica 4.1.10 para comunicar la estructura de datos referenciada. Reescriba la práctica de la suma de prefijos sustituyendo la operación de suma por la operación producto de matrices. Suponga que cada proceso tiene al comienzo una matriz 2x2. Para hacer el producto de matrices use el módulo PDL. PDL significa Perl Data Language:

1	#!/usr/bin/perl -w
2	use PDL;
3	
4	$a = pdl [[1,2,3],[2,4,6],[3,6,9]];
5	$b = pdl [[1,2],[2,4],[3,6]];
6	$c = $a x $b; # x esta sobrecargado
7	
8	print "a = $a\nb = $b\nc = $c\n";

PDL es un módulo diseñado para el cálculo y visualización de datos cientıficos. Desgraciadamente Data::Dumper no funciona bien con PDL. Existe un reemplazo para el mismo a través del módulo PDL::IO::Dumper.

DB<1> use PDL
DB<2> $a = pdl [[1,2],[3,4]] # Creamos la matriz
DB<3> use PDL::IO::Dumper
DB<4> $b = sdump $a  # Vuelca $a en una cadena
DB<5> x $b   # Este es el aspecto de la cadena:
0  '{my($VAR1);


$VAR1 = ( double(1,2,3,4)->reshape(2,2) );

}'
DB<6> $e = eval $b # El valor retornado por el bloque es el de $VAR1
DB<7> print $e     # $e es un objeto pdl 
[
[1 2]
[3 4]
]

¿Cómo hay que modificar el algoritmo usado en 4.1.10 por el hecho de que el producto de matrices es no conmutativo?

La respuesta puede verse en el siguiente código en el que, para simplificar, sólo se muestran las operaciones de reducción y se omiten las de prefijo. Cuando ocurre la comunicación en la dimensión $i el nodo en el hipercubo alto (aquel que tiene el bit $i a 1, línea 13) debe multiplicar el valor que llega ($sum) por el que posee ($total) mientras que el que está en el hipercubo bajo (aquel que tiene el bit $i a 0) lo hace a la inversa (línea 20).

 1  sub task {
 2    my ($id, $r, $w, @args) = @_;
 3    my $dim = shift @args;
 4    my $matrix = shift @args;
 5    my $total = $matrix;
 6    my $sum; 
 7    
 8
 9    for my $i (0..$dim - 1) {
10      my $mask = 0x01 << $i;
11      my $dest = $id ^ $mask;
12      my $fh = $$w[$dest];
13      if ($id & $mask) {  
14        $sum = &receiveref($dest, $r);
15        &sendref($dest, $fh, $id, $total);
16        $total = $sum x $total;
17      } else {
18        &sendref($dest, $fh, $id, $total);
19        $sum = &receiveref($dest, $r);
20        $total = $total x $sum;
21      }
22    }
23    print "[$id] Total: $total\n";
24  }

A continuación se muestra el código para la rutina de recepción, siguiendo un protocolo similar al bosquejado en la sección 4.1.10.

 1  {
 2    my %buff;
 3    sub receiveref {
 4      my $src = shift;
 5      my $r = shift;
 6      my ($result, $orig, $msg);
 7
 8      if (defined $buff{$src}) {
 9        $result = $buff{$src};
10        delete $buff{$src};
11        return $result;
12      }
13      {
14        $msg = <$r>; chomp $msg;
15        ($orig, $msg) = split /:/, $msg, 2;
16        $msg = eval $msg;
17        return $msg if $orig == $src;
18        $buff{$orig} = $msg;
19        redo;
20      }
21    }
22  }

La subrutina receiveref recibe como primer argumento el procesador fuente del mensaje. La subrutina administra un hash %buff declárado en clausura con la subrutina, en el que se almacenan los mensajes que llegan y que no son del fuente solicitado. Cuando es llamada, la subrutina comprueba si el mensaje ya solicitado esta en el hash (línea 8). Si es asi, lo obtiene, lo elimina del hash y lo retorna (líneas 9-11). En caso contrario permanece a la espera por el canal del mensaje solicitado (líneas 13-20). Los mensajes que llegan y que no son del fuente solicitado son almacenados (línea 18). Cuando llega el mensaje solicitado termina la espera y se retorna su valor (línea 17). Escriba la subrutina sendref de envío que colabora con la subrutina de recepción descrita.