Algoritmo K-L



Descripción del Algoritmo de Kernighan-Lin

Este algoritmo de partición, que se engloba dentro de los algoritmos de migración de grupos, que son algoritmos deterministas e iterativos, fue publicado en el año 1970 por B.Kernighan y S.Lin. Se trata de un algoritmo que, en su momento, tuvo bastante éxito y que ha servido de base para el desarrollo de numerosos métodos de placement.

El objetivo de este algoritmo es dividir el circuito en dos partes, de modo que se minimice el número de nets que conectan celdas pertenecientes a particiones distintas (número de corte).

El algoritmo original supone que todas las nets del circuito conectan exactamente dos celdas y que, además, todas éstas tienen el mismo tamaño

El método comienza asignando aleatoriamente las 2N celdas a dos grupos A y B. Posteriormente, se van intercambiando celdas entre las dos particiones. Estos intercambios, implican un incremento o decremento del número de corte, que se representa mediante la ganancia g.

La ganancia g, asociada al intercambio de dos celdas cualesquiera, se obtiene a partir del parámetro D que caracteriza a cada una de las celdas. Dicho parámetro, se define como la diferencia entre el número de interconexiones de la celda que atraviesan la separación entre particiones, y el número de interconexiones que no atraviesan dicha frontera. Así, el parámetro D, asociado a una celda ai, será:

Ecuación 1

donde:

El intercambio de dos celdas ai y bi, se caracteriza mediante una ganancia gi, definida como:

Ecuación 2

Por tanto, teniendo en cuenta la definición del parámetro D, es fácil deducir que, tal y como habíamos afirmado previamente, la ganancia gi representa la modificación en el número de cortes que implica el intercambio de ai y bi.

El primer paso es seleccionar dos celdas, a1 y b1, pertenecientes, respectivamente, a los grupos A y B, de modo que la ganancia g1 asociada al intercambio de estos dos elementos sea mínima y, por tanto, la reducción del número de corte sea máxima. A continuación, se intercambian las celdas y, durante las iteraciones restantes, se impiden nuevos desplazamientos de las mismas.

El siguiente paso es seleccionar dos nuevas celdas, a2 y b2, cuyo intercambio ha de suponer un incremento mínimo, g2, del número de corte. Una vez realizado el intercambio, se bloquean nuevos desplazamientos de estos dos elementos. Esta serie de pasos continúa hasta que todos los elementos del circuito han sido bloqueados. En ese instante, tendremos en A todas las celdas que antes estaban en B y, en B, todas las celdas que antes estaban en A. Por tanto, tras realizar N intercambios, se tiene:

Ecuación 3

Es preciso tener en cuenta que, la ganancia asociada a alguno de los N intercambios realizados, puede ser positiva o nula. Ésta es la clave del algoritmo de Kernighan-Lin pues, teniendo en cuenta la apreciación anterior, su objetivo es encontrar aquel valor de k que minimiza:

Ecuación 4

Tras encontrar este valor, se confirma el desplazamiento de las celdas a1, a2,a3, ...,ak al conjunto B, y el de las celdas b1, b2, b3, ...,bk al conjunto A, mientras que, los restantes intercambios se cancelan. Puede ocurrir que, para el valor de k elegido, algunos de los intercambios incrementen el número de corte, sin embargo, el decremento total es máximo. Éste método, consistente en permitir intercambios que incrementen el número de corte, trata de evitar, en lo posible, los mínimos locales.

A continuación, tienen lugar una serie de iteraciones en las que se realizan nuevos intercambios y se selecciona el valor de k que optimiza la reducción del número de corte. El proceso continúa hasta que, en una de las iteraciones se cumple que:

Ecuaci&oaciye;n 5


Descripción de la implementación realizada

Este algoritmo se ha implementado en lenguaje C. El programa se puede ejecutar en entorno MS-DOS, para lo cual simplemente hay que teclear partitio desde el directorio en el que se encuentre el programa, o en entorno Windows. En este último caso, hay que seguir la siguiente secuencia de pasos: inicio>ejecutar>teclear "partitio" precedido del path correspondiente>pulsar INTRO. Estos pasos se muestran en las dos figuras siguientes.

Panel de inicio Ventana de ejecución del programa

Al ejecutar el programa partitio.exe, el usuario ha de elegir la opción Kernighan-Lin y proporcionar un fichero de entrada que contenga el número de bloques así como las interconexiones entre ellos. A partir de esta información, se distribuyen los bloques en dos particiones, utilizando un método constructivo determinista; opcionalmente, es posible visualizar una representación gráfica de esta distribución. El siguiente paso es la ejecución del algoritmo, tras lo cual, también opcionalmente, es posible visualizar el reparto final de los elementos. Por último, se genera el fichero de salida, en el que se indica la distribución de los bloques obtenida.

Formato del fichero de entrada

  • Primera línea: Número de bloques del sistema (2N).

  • Líneas siguientes: Tiene que haber tantas líneas como bloques. La correspondencia entre líneas y bloques es secuencial, i.e., la línea 2 corresponde al bloque 1, la línea 3 corresponde al bloque 2,... y la línea (2N+1) corresponde al bloque 2N. En cada una de estas líneas, se indica el número de interconexiones del bloque y los identificadores de los bloques a él conectados; todo ello separado por comas.
  • Ejemplo de fichero de entrada

    8
    3,2,5,6
    3,1,5,6
    4,4,6,7,8
    3,3,7,8
    3,1,2,6
    4,1,2,3,5
    3,3,4,8
    3,3,4,7

    Formato del fichero de salida

    El fichero de salida tiene cinco líneas. En la primera, se indica a qué fichero de entrada corresponden los resultados. En las líneas 2 y 4, se indican las particiones, y, en las líneas 3 y 5, se presentan, separados por espacios en blanco, los bloques asignados a las particiones 1 y 2, respectivamente.

    Ejemplo de fichero de salida

    //Resultados de la partición del fichero bloques.txt.
    PARTICIÓN 1:
    1 2 5 6
    PARTICIÓN 2:
    3 4 7 8

    A continuación, se muestra la representación de las distribuciones inicial y final de los bloques, correspondientes al ejemplo cuyo fichero de entrada se ha presentado anteriormente. Como se puede observar, el algoritmo consigue reducir el número de cortes de 9 a 1.

    Partición inicial
    Ejemplo de entrada para el algoritmo K-L


    Partición final
    Resultado del algoritmo K-L





    Volver a la página inicial