ES2206862T3 - Dispositivo de seleccion de elementos de datos de arbol binario y espaciador atm que comprende dicho dispositivo. - Google Patents

Abstract

PARA SELECCIONAR ELEMENTOS DE DATOS QUE INCLUYAN UNA CLAVE DE SELECCION, SE ORGANIZAN MEDIOS DE MEMORIZACION DE ACUERDO CON UN ARBOL BINARIO DE 2 N - 1 NUDOS CAPACES DE CONTENER CADA UNO UN ELEMENTO Y REPARTIDOS EN N ETAPAS SUCESIVAS NUMERADAS DE 0 A N - 1, CONTENIENDO LA ETAPA Q LOS NUDOS 2 Q A 2 Q+1 -1. LOS ELEMENTOS ESTAN DISTRIBUIDOS EN EL ARBOL DE FORMA QUE CADA ELEMENTO CONTENIDO EN UN NUDO I TENGA UNA CLAVE DE SELECCION MAS PEQUEÑA QUE LAS DE LOS ELEMENTOS CONTENIDOS EN LOS NUDOS 2I Y 2I + 1. EL ARBOL ESTA GESTIONADO POR M CONTROLADORES SUCESIVOS (21 Q ) ASOCIADOS CADA UNO A UNA ETAPA (2 0 Q ) O A VARIAS ETAPAS CONSECUTIVAS DEL ARBOL (2 M N), CON N - 1 REGISTROS DE INTERFAZ (26 Q ) ENTRE ETAPAS SUCESIVAS, DE LAS QUE LAS SITUADOS ENTRE LOS CONTROLADORES SON REGISTROS PIPE-LINE QUE PERMITEN UN TRABAJO EN PARALELO DE LOS CONTROLADORES PARA MODIFICAR EL CONTENIDO DEL ARBOL CON MOTIVO DE COMANDOS DE CAMBIO O DE INSERCION PROPAGADOS DESDE LA ETAPA 0 A LA ETAPA N - 1.

Description

Dispositivo de selección de elementos de datos de árbol binario y espaciador ATM que comprende dicho dispositivo.

La presente invención se refiere de un dispositivo de selección de elementos de datos que incluyen cada uno una clave de selección respectiva, que comprende:

-

unos medios de memorización organizados según un árbol binario de 2^{n}-1 nudos numerados de 1 a 2^{n}-1 aptos para contener cada uno un elemento de datos y repartidos en n niveles sucesivos numerados de 0 a n-1, comprendiendo el nivel q los nudos 2^{q} a 2^{q+1-}1; y

-

unos medios de control del árbol binario para distribuir los elementos a seleccionar en el árbol de manera que verifiquen una condición de ordenamiento según la cual, para cada entero i comprendido entre 1 y 2^{n-1-}1 tal que el nudo i contenga un elemento a seleccionar, cada uno de los nudos 2i y 2i+1 o bien no contiene ningún elemento a seleccionar, o bien contiene un elemento cuya clave de selección es superior o igual, en el sentido de una relación de orden determinada, a la clave de selección del elemento contenido en el nudo i.

El ordenamiento de los elementos en el árbol de selección corresponde a lo que se denomina la "selección por montón" ("heapsort") en el campo de la selección informática. Se podrá hacer referencia a este respecto a la obra de Knuth: "The art of computer programming, vol. 2, Sorting and searching", Addison Wesley, 1973, páginas 142-157.

A título de ilustración, la figura 1 muestra, en el caso en que n=4, un árbol de selección que comprende quince nudos 1-15 que contienen unos elementos de datos (de las cuales la clave de selección está representada) que verifican la condición de ordenamiento.

El nudo 1 del nivel 0 se denomina vértice o raíz del árbol. Los 2^{n-1} nudos 2^{n-1} a 2^{n}-1 del nivel n-1 se denominan hojas del árbol. Para cada nudo i de un nivel q, los 2^{n-q}-1 nudos del árbol cuyos números son de la forma i2^{j}+j', donde j y j' son unos enteros tales que 0 \leq j <n-q y 0\leqj'<2^{j}, se denominan descendientes del nudo i (se considera aquí que el nudo i está incluido en sus descendientes). Entre estos descendientes, los nudos hermanos 2i y 2i+1 del nivel q+1 (si q<n-1) se denominan hijos del nudo i. El padre del nudo i (si q>0) es por otra parte definido como el nudo del nivel q-1 cuyo número es i/2 si i es par y (i-1)/2 si i es impar. Estas relaciones lógicas de filiación entre los nudos del árbol están representados por unas flechas en la figura 1.

La relación de orden entre las claves de selección es arbitraria. En el caso ilustrado por la figura 1, se trata de la relación de orden familiar entre los enteros naturales, que permiten una selección de orden creciente de las claves de selección. En el caso de una selección en orden decreciente, es suficiente claramente invertir la relación de orden entre las claves. En la figura 1, se ha considerado que los nudos del árbol no ocupados por los elementos a seleccionar contienen cada uno un elemento cuya clave de selección es infinita, es decir superior a cualquier clave de selección de un elemento de datos a seleccionar. Una posibilidad para codificar una clave infinita es reservar a este fin un bit del campo de datos que contiene la clave; la clave será por ejemplo considerada como infinita si este bit es de 1 y si no como finita; en otros términos, este bit indica si el nudo está libre u ocupado por un elemento de datos.

Una vez que está cargado con un conjunto de N<2^{n} elementos de datos ordenados, el dispositivo de selección es capaz de suministrar secuencialmente estos N elementos en N ciclos en el orden de las claves de selección. La extracción de un elemento del árbol en el curso de un ciclo consiste en leer el elemento situado en el vértice del árbol y en hacer subir unos elementos de su descendencia de manera que verifiquen siempre la condición de ordenamiento. Así, en el caso representado en la figura 1, el primer ciclo consiste en leer el elemento 16 situado en el vértice, y en desplazar el elemento 24 hacia el vértice, y después el elemento 38 hacia el nudo 2 y por último el elemento 623 hacia el nudo 4. Esto vuelve a propagar el mando de extracción desde el vértice en dirección a las hojas.

En cierto número de aplicaciones, es necesario que los medios de control sean también capaces de responder a unos mandos de inserción de un nuevo elemento a seleccionar en el árbol. El dispositivo de selección es entonces capaz de suministrar o de recibir en cada ciclo unos elementos a seleccionar. Funciona como una fila de espera dinámica sobre la base de las claves de selección, administradas según la relación de orden utilizada, y que pueden representar unas etiquetas temporales o cualquier otro tipo de índice de prioridad.

En los árboles binarios de selección conocidos, el mando de inserción no es propagado del vértice hacia las hojas del árbol puesto que, a nivel de un nudo dado, no se sabe a priori hacia cuál de los dos hijos debe ser propagado el mando, observándose que uno de los dos hijos puede tener su descendencia completamente ocupada y por tanto no ser apropiado para recibir el mando. El mando de inserción es por tanto propagado desde las hojas del árbol hacia el vértice. Por ejemplo, para insertar en el árbol de la figura 1 un elemento cuya clave de selección es 28, se escribe en una hoja libre del árbol, por ejemplo la hoja 9, y se realizan progresivamente unas comparaciones con los elementos contenidos en los nudos ascendentes; así, los elementos 28 y 38 será permutados para restablecer el ordenamiento en el ejemplo considerado.

En estas condiciones, es necesario que el ciclo precedente esté acabado en el momento de extraer el elemento del árbol que tiene la clave más pequeña. En consecuencia, el caudal al cual el dispositivo puede suministrar o recibir unos elementos de datos está limitado por la duración del ciclo de tratamiento de un mando, que es proporcional al número de niveles n, es decir al logaritmo del número máximo N de elementos a seleccionar. En unas aplicaciones en las que este número N es importante, por ejemplo algunos millares, y en las que se requiere un caudal elevado, por ejemplo superior a 500.000 elementos por segundo, el dispositivo de selección ya no es realizable con los circuitos electrónicos conocidos.

En su artículo "A real time sorter with application to ATM traffic control" (Proc. ISS'95, abril 1995, Volumen 1, páginas 258-262), J.W. Roberts et al han descrito un dispositivo de selección que no adolece de la limitación de caudal anterior, es decir capaz de suministrar y de recibir los elementos a una cadencia a priori independiente del número máximo de elementos a seleccionar. Pero un inconveniente de este último dispositivo es que el número de circuitos lógicos que funcionan en paralelo es proporcional a N. En cuanto el número N de elementos a seleccionar resulta importante (algunos millares o decenas de millares como en el caso de aplicación a un espaciador de células ATM previsto en el artículo), la complejidad material del dispositivo se vuelve redibitoria.

Los artículos de C. THOMPSON titulado "The VLSI Complexity of Sorting" IEEE TRANSACTIONS ON COMPUTERS., vol. c-32, nº 12, diciembre 1983, páginas 1171-1184, XP002053125, NEW YORK, US y de TANAKA Y ET AL titulado "Pipeline searching and sorting modules as components of a data flow database computer" INFORMATION PROCESSING 80, PROCEEDINGS OF THE IFIP CONGRESS 80, TOKYO, JAPAN, 6-9 OCT. 1980, páginas 427-432, XP002053126 ISBN 0-444-086034-7, 1980, AMSTERDAM, NETHERLANDS, NORTH-HOLLAND, NETHERLANDS hacen mención del dispositivo de selección del tipo "heapsort" basado en un tratamiento en modo pipeline.

Un objetivo de la presente invención es proporcionar un dispositivo de selección rápido y de complejidad limitada.

La invención propone así un dispositivo del tipo indicado en la introducción, en el cual los medios de control responden a unos mandos de modificación del contenido del árbol binario que incluyen unos mandos de inserción de un nuevo elemento a seleccionar. Según la invención, los medios de control comprenden m controladores sucesivos asociados cada uno a un nivel 0 a varios niveles consecutivos del árbol binario, siendo m un entero comprendido entre 2 y n, y n-1 registros de intercara entre niveles sucesivos, entre los cuales cada uno de los m-1 registros de intercara entre pares de niveles asociados a unos controladores diferentes constituye un registro pipeline, y en el cual cada mando de modificación del contenido del árbol binario es propagado del nivel 0 hacia el nivel n-1 por medio de los registros de intercara, permitiendo el o los registros pipeline un trabajo en paralelo de los controladores.

La complejidad del dispositivo está limitada por el número m de controladores que es a su vez como máximo igual al número n de niveles del árbol, es decir al logaritmo del número máximo de elementos a seleccionar. La organización en pipeline de los controladores permite un trabajo en paralelo y una gran cadencia de entrada y de salida de elementos a seleccionar. Esta cadencia es independiente del número de elementos a seleccionar. La misma es máxima cuando el número m de controladores es igual al número n de niveles.

El dispositivo de selección según la invención puede tener diversas aplicaciones, cuando se necesita una selección rápida de elementos de datos cuyo número puede ser importante. Puede así ser realizado en forma de una tarjeta de coprocesador de selección para cualquier sistema informático. Un campo de aplicación interesante es el del ordenamiento de procesos: las claves de selección representan entonces unos instantes en los que se requiere activar unos procesos. Se puede entonces extraer en cada instante del árbol el elemento más "urgente".

El dispositivo según la invención tiene una aplicación particularmente ventajosa en el campo del espaciado de células ATM. Un segundo aspecto de la invención propone así un espaciador de células ATM transmitidas según un conjunto de conexiones virtuales, que comprende una memoria de células en la cual unas células entrantes se escriben y unas células salientes se leen, y unos medios para atribuir una hora teórica de emisión a cada célula almacenada en la memoria de células. Según la invención, el espaciador comprende además unos medios de control de espaciado para administrar la memoria de células, con la ayuda de una memoria de apuntadores asociada, de manera que la memoria de células comprende, para cada conexión virtual para la cual contiene unas células, una lista de emplazamientos en los que estas células son ordenadas en modo primero en entrar-primero en salir entre una cabeza de lista y un final de lista, y unos medios de selección para ordenar unos elementos de datos que comprenden cada uno una identidad de conexión virtual y una clave de selección que consiste en la hora teórica de misión de la célula contenida en la cabeza de lista relativa a dicha conexión virtual, y para seleccionar por lo menos un elemento de datos que tiene una clave de selección mínima, estando los medios de control de espaciado dispuestos para mandar la emisión de una célula contenida en la cabeza de lista relativa a una conexión virtual identificada en un elemento de datos seleccionado por los medios de selección, y los medios de selección que comprenden por lo menos un dispositivo de selección tal como el definido anteriormente, cuyo nudo 1 del nivel 0 contiene dicho elemento seleccionado.

Otras particularidades y ventajas de la presente invención se pondrán de manifiesto a partir de la descripción siguiente de ejemplos de realización no limitativos, con referencia a los planos anexos, en los cuales:

- la figura 1 es un esquema de un árbol binario de selección;

- la figura 2 es un esquema sinóptico de un dispositivo de selección utilizable según la invención;

- la figura 3 es un esquema sinóptico que muestra el entorno de cada controlador del dispositivo de la figura 2;

- las figuras 4A a 4C muestran un organigrama del funcionamiento del controlador de la figura 3;

- la figura 5 muestra un cronograma del funcionamiento del dispositivo de selección;

- las figuras 6 y 7 son unos esquemas semejantes al de la figura 3 y que muestran unas variantes posibles para el entorno de los controladores;

- la figura 8 es un esquema que muestra un registro con desplazamiento utilizable con un dispositivo de selección según la figura 7;

- la figura 9 muestra un cronograma simplificado del dispositivo de selección;

- las figuras 10A y 10B, que deben completarse con la figura 4C, muestran un organigrama del funcionamiento del controlador de la figura 7;

- las figuras 11A y 11B, que deben completarse con la figura 4C, muestran un organigrama correspondiente al de las figuras 10A, 10B y 4C en el caso particular del último nivel del árbol binario;

- la figura 12 es un esquema de conjunto de un espaciador de células ATM que utiliza la presente invención;

- la figura 13 muestra unos cronogramas del funcionamiento del espaciador de la figura 12;

- las figuras 14 y 15 son unos organigramas que muestran respectivamente las operaciones efectuadas por el controlador del espaciador de la figura 12 cuando tiene lugar la recepción y la emisión de una célula ATM; y

- las figuras 16 y 17 son unos esquemas parciales de variantes de espaciadores ATM que utilizan la presente invención.

La figura 2 muestra un dispositivo de selección en el cual los elementos de datos están contenidos en una memoria 20_{0}-20_{3} organizada de acuerdo con el árbol binario de la figura 1, con n=4 niveles.

El árbol binario es controlado por un conjunto de m controladores distintos, donde m es un entero comprendido entre 2 y el número n de niveles del árbol. En el caso considerado en las figuras 2 y 3, hay un controlador 21_{q} para cada nivel q del árbol, o sea m=n=4. Cada controlador 21_{q} comprende un bus 22_{q} que le permite acceder al nivel q. Los medios de memorización del árbol están así divididos en m=4 módulos de memoria 20_{0}-20_{3} accesibles cada uno por un bus respectivo 22_{0}-22_{3}. En cada nudo i se encuentran dos emplazamientos de memoria para contener respectivamente la clave de selección K(i) de un elemento de datos, representada sola en la figura 2 (K(i) = \infty en ausencia de elemento), y una referencia R(i) de este elemento (ver figura 3).

Cada nivel q del árbol distinto del nivel 0 comprende, además de los nudos 2^{q} a 2^{q+1}-1, 2^{q-1} emplazamientos 23 de 1 bit de capacidad, y 2^{q-1}emplazamientos 25 de n-q+1 bits de capacidad n-q+1 bits. Cada emplazamiento 23 contiene un bit de orientación F(i) asociado a un par de nudos hermanos 2i y 2i+1 del nivel q, cuyo valor es F(i)=0 si la clave contenida en el hermano de la izquierda 2i es inferior a la contenida en el hermano de la derecha 2i+1 (K(2i)<K (2i+1)), y F(i)=1 si K(2i+1)\leqK(2i). El número total de emplazamientos 23 en el árbol de selección es 2^{n-1}-1.

Cada emplazamiento 25 del nivel q contiene un contador diferencial \Delta(i) asociado a un par de nudos hermanos 2i y 2i+1 del nivel q, cuyo valor viene dado por la diferencia entre el número de elementos de datos contenidos en los descendientes del hermano de la izquierda 2i y el número de elementos de datos contenidos en los descendientes del hermano de la derecha 2i+1.

Los bits de orientación F(i) sirven para propagar los mandos de extracción o de intercambio del vértice hacia las hojas del árbol, mientras que los contadores diferenciales \Delta(i) sirven para propagar los mandos de inserción del vértice hacia las hojas del árbol.

Los medios de control del árbol binario comprenden además n-1=3 registros de intercara 26_{1}-26_{3}, sirviendo cada registro 26_{q} de intercara entre el controlador 21_{q-1} del nivel q-1 y el controlador 21_{q} del nivel q. En el esquema de principio de la figura 2, se ha representado además un registro 26_{0} que sirve de intercara entre el controlador 21_{0} del nivel 0 y el entorno del dispositivo de selección. Los mandos enviados al dispositivo de selección se escriben en este registro 26_{0} así como las respuestas proporcionadas por el dispositivo de selección. En la práctica, este registro 26_{0} puede pertenecer al mismo circuito que el controlador 21_{0} del nivel superior del árbol.

Con referencia a la figura 3, cada registro 26_{q} se compone de cuatro emplazamientos que

\hbox{contienen respectivamente:}

-

un código de mando A_{q} que designa la naturaleza del mando propagado del vértice hacia las hojas del árbol; en la continuación de la exposición, se considerará a título de ejemplo que los mandos A_{q} están codificados sobre dos bits de la forma siguiente: A_{q}=00 para una ausencia de modificación del contenido del árbol a partir del nivel q, A_{q} =01 para un mando de inserción de un nuevo elemento, A_{q} = 11 para un mando de intercambio que consiste en extraer del árbol el elemento que tiene la menor clave de selección al mismo tiempo que se inserta en el mismo un nuevo elemento (la extracción simple del elemento que tiene la clave más pequeña de selección es tratada como el intercambio de este elemento con un elemento que tiene una clave de selección infinita), y A_{q}=10 para un mando de reinicialización del contenido del árbol a partir del nivel q;

-

una clave de selección B_{q} transmitida del nivel q-1 hacia el nivel q cuando tiene lugar un mando de inserción o de intercambio, o del nivel q hacia el nivel q-1 cuando tiene lugar un mando de intercambio;

-

una referencia C_{q} asociada a la clave de selección B_{q} y que forma con ésta un elemento de datos insertado o intercambiado; y

-

una identificación D_{q} que se compone de q-1 bits (esta identificación no existe en el registro 26_{0}), que designa el nudo del nivel q-1 de donde proviene el mando A_{q}. Más precisamente, la identificación D_{q} está constituida por los q-1 bits de peso más bajo de la representación binaria del número del nudo i del nivel q-1 desde donde proviene el mando A_{q}, es decir que i=1D_{q} en base 2.

Para insertar un nuevo elemento en el árbol, se inscribe el mando A_{0}=01, y este nuevo elemento B_{0}, C_{0}, en el registro 26_{0}, y el mando es a continuación propagado del vértice hacia las hojas del árbol. Para efectuar un intercambio, se escribe el mando A_{0}=11 y el elemento B_{0}, C_{0} a insertar en el registro 26_{0} (con B_{0}= \infty en el caso de una extracción simple), y después se recupera el elemento que tiene la clave más pequeña en los emplazamientos B_{0} y C_{0} del registro 26_{0}.

Las operaciones efectuadas por cada controlador 21_{q} están representadas en el organigrama de las figuras 4A, 4B y 4C. Para la ejecución de estas operaciones, cada controlador 21_{q} está realizado en forma de una red de puertas lógicas rápidas convenientemente programada. Al ser las operaciones esencialmente unas lecturas/escrituras, unos incrementos/decrementos y unas comparaciones de variables codificadas en binario, esta programación de la red de puertas no plantea ningún problema.

El mando A_{q} es en principio leído en el registro 26_{q} (etapa 100) y después evaluado (etapas 101) para identificar el tipo de mando.

En el caso de una ausencia de modificación (A_{q}=00), el controlado 21_{q} escribe simplemente el mismo mando A_{q+1} = 00 en el registro siguiente 26_{q+1} (etapa 102).

En el caso de un mando de reinicialización (A_{q} =10), la identificación D_{q} del padre es asignada a la variable s (etapa 103), y el controlador 21_{q} inicializa los dos nudos hijos, cuyos números tienen como representaciones binarias 1s0 y 1s1, poniendo su clave de selección en el infinito y el valor 0 en el contador diferencial asociado \Delta(1s) (etapa 104), antes de propagar el mando A_{q+1}=00 en la etapa 102. En el caso particular del nivel 0, la reinicialización consiste solamente en escribir K(1)=\infty.

Cuando el mando A_{q} leído en el registro 100 se refiere a la inserción de un nuevo elemento B_{q}, C_{q} desde un nuevo padre 1D_{q} (A_{q}=01), estos parámetros B_{q}, C_{q} y D_{q} son respectivamente leídos por el controlador 21_{q} y asignados a unas variables k, r y s en la etapa 105, y después el contador diferencial \Delta(1s) asociado a los hijos del nudo identificado es asignado a la variable \delta en la etapa 106.

Si \delta < 0 (comparación 107), el hijo derecho tiene una descendencia más numerosa que el hijo izquierdo, y se tiene la seguridad de que el hijo izquierdo tiene en su descendencia por lo menos un nudo capaz de recibir el nuevo elemento, de manera que el mando de inserción sea propagado hacia el hijo izquierdo. El bit t es entonces igual a 0, y la variable \delta incrementada en una unidad en la etapa 108. Inversamente, si \delta \geq 0, el bit t es igual a 1, y la variable \delta decrementada en una unidad en la etapa 109 para propagar el mando de inserción hacia el hijo derecho. En la etapa 110, la clave de selección K(1st) y la referencia R(1st) del elemento de datos contenido en el nudo tratado, es decir aquél hacia el cual es propagado el mando, son leídos y respectivamente asignados a las variables
k' y r'.

Si k<k' (comparación 111), el nudo tratado contiene una clave de selección mayor que el elemento de datos a insertar, de manera que el elemento w, x que será propagado hacia el nivel q+1 es tomado, en la etapa 112, igual al k', r' leído en el nudo tratado. Si k '\leq k , el elemento a transmitir w, x es tomado, en la etapa 113, igual al k, r leído en el registro 26_{q} en la etapa 113, y después las variables k, r reciben respectivamente los valores de las variables k', r'.

Si la clave w del elemento de datos a propagar es infinita (comparación 114), es que el mando de inserción ya no ha de ser propagada. El procesador 21_{q} da entonces el valor 10 (reinicialización) a la variable v' en la etapa 115. Si la clave w a transmitir es finita, la variable v' recibe el valor 01 en la etapa 116 para indicar un mando de inserción. El procesador 21_{q} puede a continuación llenar el registro 26_{q+1} escribiendo en el mismo A_{q+1}=v', B_{q+1}=w, C_{q+1} = x y D_{q+1}=st en la etapa 117.

Después de la etapa 117, el tratamiento del mando de inserción no necesita ya que el controlador 21_{q} acceda a sus registros de intercara 26_{q}, 26_{q+1}, sino solamente a la zona de memoria 20_{q} que trata. En la etapa 118, actualiza el contador diferencial \Delta(1s) escribiendo en el mismo el nuevo valor de la variable \delta. Después, en la etapa 119, actualiza el elemento de datos del nudo tratado escribiendo en el mismo K(1st)=k y R(1st)=r.

El controlador 21_{q} sólo debe entonces, para acabar el tratamiento del mando de inserción, actualizar el valor del bit de orientación F(1s) asociado al nudo tratado 1st. El controlador 21_{q} lee en primer lugar la clave de selección K(1st) del elemento de datos contenido en el nudo hermano del nudo tratado, y lo asigna a la variable k'. La variable f, que será escrita en el emplazamiento 23 que contiene el bit de orientación F(1s) en la etapa 126, es tomada igual a 1 en la etapa 124 (orientación hacia el hijo derecho) si las comparaciones 121, 122 y 123 muestran que t=0 y k'\leqk, o que t=1 y k\leqk'. En el caso contrario, se toma f=0 en la etapa 125.

Después de la etapa 126, el procesador 21_{q} ha terminado de tratar el mando A_{q} y puede volver a la etapa 100 para tratar el próximo mando que proviene del registro 26_{q}.

Cuando el mando leído en el registro 26_{q} se refiere al intercambio del elemento de datos B_{q}, C_{q} desde un nudo padre 1D_{q} del nivel q -1 (A_{q}=11), estos parámetros B_{q}, C_{q} y D_{q} son leídos y respectivamente asignados a las variables k, r y s en la etapa 130, y después el valor del bit de orientación F(1s) asociado a los dos hijos del nudo identificado es asignado al bit t en la etapa 131. Los datos K(1st), R(1st) leídos en el nudo tratado 1st son entonces asignados a las variables k' y r' en la etapa 132.

Si el nudo tratado contiene una clave de selección superior a la del elemento de datos leído en el registro 26_{q} (k<k' cuando tiene lugar la comparación 133), el mando de intercambio no tiene necesidad de ser propagado hacia los niveles inferiores del árbol, de manera que el mando v' que será descrito en el registro 26_{q+1} es tomado igual a 00 (ausencia de modificación) en la etapa 134. En esta etapa 134, el elemento de datos w', x', que será enviado de nuevo al registro 26_{q}, es además tomado igual al k, r que tiene la clave de selección más pequeña. Si la comparación 133 muestra que k \geq k', la etapa 134 es reemplazada por una etapa 135 en la cual el procesador 21_{q} toma w' = k', x'=r' y v'=11 (propagación del mando de intercambio).

El procesador 21_{q} procede entonces a la etapa 136 donde escribe el elemento w', x', en los emplazamientos B_{q} y C_{q} del registro de intercara 26_{q}.

Para propagar el mando, el controlador 21_{q} ejecuta a continuación la etapa 137, en la que escribe en el registro de intercara 26_{q+1}: A_{q+1}=v', B_{q+1}=k, C_{q+1}=r y D_{q+1}=st.

Si el mando propagado no es una mando de intercambio, es decir si la comparación 138 muestra que v'\neq11, el tratamiento del mando de intercambio por el controlador 21_{q} ha terminado después de la etapa de escritura 137. Si no, el procesador 21_{q} pasa a la etapa 139 en la que examina si la clave k que ha transmitido hacia el nivel q+1 es infinita

\hbox{o no.}

Si la comparación 139 muestra que k = \infty, entonces el mando de intercambio es de hecho un mando de extracción simple, y es necesario actualizar el contador diferencial \Delta(1s) asociado al nudo tratado. El valor de este contador diferencial es en principio leído y asignado a la variable \delta en la etapa 140. Si el controlador 21_{q} ha tratado un hijo izquierdo (t=0 cuando tiene lugar la comparación 141), la variable \delta es decrementada en una unidad en la etapa 142, mientras que es incrementada en una unidad en la etapa 143 en el caso contrario. El contador diferencial \Delta(1s) es a continuación puesto al día en la etapa 144 según el nuevo valor de la variable \delta.

Dado que el intercambio de dos elementos que tienen cada uno una clave de selección finita no afecta a los valores de los contadores diferenciales, las etapas 140 a 144 no son ejecutadas si la comparación 139 muestra que la clave transmitida k es finita.

El procesador 21_{q} prosigue entonces el tratamiento del mando de intercambio en la etapa 145 leyendo el elemento de datos B_{q+1}, C_{q+1} que el controlador 21_{q+1} ha enviado de nuevo (cuando tiene lugar su etapa 136) al registro 26_{q+1}, y asignado este elemento reenviado a las variables k y r. El tratamiento del mando termina a continuación por las etapas 119 a 126 tales como las descritas anteriormente.

El organigrama de las figuras 4A-4C ha sido presentado en el caso de un nivel q cualquiera. Desde luego, algunas adaptaciones son necesarias para el primer nivel q=0 y el último nivel q=n-1. Así, para q=0, el nudo tratado 1st se entiende como que es siempre el vértice del árbol, pudiendo las etapas 106-109, 118, 120-127, 131 y 139-144 ser suprimidas. Dado que no es necesario prever un registro 26_{n} corriente abajo del último controlador, las etapas 110 a 117 pueden ser suprimidas en lo que concierne al último nivel n-1 así como las etapas 102, 137 y 145 y, solamente para el intercambio, la etapa 119.

La organización temporal del trabajo en paralelo de los controladores sucesivos está condicionada por la repartición del acceso a los registros de intercara 26_{q}. En las figuras 4A y 4B, se ha indicado en el instante \alpha_{q} en que el controlador 21_{q} ha terminado de escribir en el registro 26_{q+1} el mando que transmite así como los parámetros asociados (después de la etapa 102, 117 ó 137 según el tipo de mando), así como, en el caso de un mando de intercambio, el instante \beta_{q} en el que el controlador 21_{q} ha terminado de escribir en el registro 26_{q} el elemento de datos B_{q}, C_{q} que reenvía hacia el controlador 21_{q-1}. Se designa además por \alpha'_{q} el instante en que el controlador 21_{q} empieza a leer un nuevo mando en el registro 26_{q} (inmediatamente antes de la etapa 100), y por \beta'_{q} el instante en que el controlador 21_{q} empieza a leer en el registro 26_{q+1} el elemento de datos reenviado por el controlador 21_{q+1} en el caso de un mando de intercambio (inmediatamente antes de la etapa 145). Para obtener un funcionamiento correcto en pipeline, es suficiente disponer los controladores de tal manera que, para cada mando, se tenga \alpha_{q} \leq \alpha'_{q+1} y \beta_{q} \leq \beta_{q-1}.

Para verificar estas dos condiciones, los controladores 21_{q} pueden ser asíncronos o síncronos. En el primer caso, el funcionamiento en pipeline está asegurado con la ayuda de señales de acuse de recibo intercambiadas entre los controladores. Después de haber ejecutado su etapa 136, el controlador 21_{q} envía una señal de acuse de recibo hacia el controlador 21_{q-1} que sabe entonces que puede proceder a su etapa 145 y a la continuación del tratamiento del mando de intercambio. Además, después de haber ejecutado la etapa 102 ó 137 ó 117, el controlador 21_{q} envía una señal de acuse de recibo al controlador 21_{q+1} que sabe entonces que puede empezar a tratar el mando procediendo a su etapa de lectura 100.

Un funcionamiento síncrono de los controladores 21_{q} será a menudo de una instalación más cómoda en el caso en que los controladores son realizados a partir de redes de puertas lógicas. La organización del pipeline en este caso está ilustrada por los cronogramas de la figura 5.

En esta figura, cada una de las cuatro líneas ilustra el funcionamiento del controlador de uno de los niveles. Las letras RD y WR encima de la línea relativa a nivel q, representan respectivamente una lectura y una escritura efectuadas por el controlador 21_{q} en el registro 26_{q}, mientras que estas mismas letras situadas debajo de la línea indican respectivamente una lectura y una escritura en el registro 26_{q+1}. Las flechas entre niveles representan así las transferencias de mando y de parámetros por medio de los registros pipeline. Los intervalos rayados representan los instantes en los que el controlador 21_{q} trabaja sobre la zona de memoria 20_{q} que controla.

El período \theta_{1} indicado en la figura 5 determina la cadencia a la cual el dispositivo de selección puede recibir nuevos elementos y suministrar los elementos que tienen las claves de selección más pequeñas. La misma corresponde a la duración que necesita cada controlador para tratar el conjunto de las instrucciones relativas a un mando. Se observa que este período \theta_{1} es sensiblemente más corto que la duración del ciclo \theta_{2} que es necesario para restablecer la regla de ordenamiento en el conjunto del árbol de selección después de que un nuevo mando ha empezado a ser tratado. En el ejemplo representado en la figura 5, el primer período \theta_{1} corresponde al intercambio del elemento situado en el vértice del árbol con otro elemento que viene a colocarse en el nivel 1 (es decir que, en el caso de la figura 2, su clave está comprendida entre 25 y 38), y el segundo período \theta_{1} corresponde a la inserción de un nuevo elemento hasta el nivel 2 (la clave es superior o igual a la del elemento introducido cuando tiene lugar la operación de intercambio precedente).

Se observa también que el tiempo de respuesta \theta_{0}-\beta_{0}-\alpha'_{0} para que el dispositivo reenvíe al registro 26_{0} el elemento de datos que tiene la clave de selección mínima corresponde aproximadamente a un tercio del período \theta_{1}.

Para minimizar el período \theta_{1}, y por tanto maximizar la cadencia de funcionamiento del dispositivo de selección, es interesante distribuir de forma homogénea los tratamientos efectuados por los controladores en los intervalos que separan los instantes en los que acceden a sus registros de intercara. Esto puede ser realizado desplazando el tratamiento de algunas instrucciones del organigrama de las figuras 4A a 4C. Si, por ejemplo, existen antes de los instantes \beta'_{q} unos lapsos de tiempo 146 (figura 5) en los que el controlador q debe esperar a que el controlador 21_{q+1} haya terminado de ejecutar su serie de instrucciones 130-136 antes de leer su resultado en el registro 26_{q+1}, es posible llenar por lo menos en parte este lapso de tiempo por la ejecución de otras instrucciones, lo que permitirá ganar tiempo por otra parte. Así, por ejemplo, en el caso de las figuras 4A-4C, la lectura 120 de la clave de selección del hermano del nudo tratado podría ser efectuada antes de la etapa 145 en una operación de intercambio y después de la etapa 118 en una operación de inserción. Este tipo de optimización depende ampliamente de las elecciones de arquitectura realizadas para programar las redes de puertas lógicas.

En la descripción anterior, se ha considerado el caso en que cada uno de los controladores está asociado a un solo nivel del árbol binario cuyo acceso le está reservado, lo que da al dispositivo las mejores características de rapidez. La complejidad del dispositivo, medida en número de circuitos lógicos (controladores 21_{q}) necesarios para su funcionamiento, es entonces de n, es decir el logaritmo del número máximo de elementos a seleccionar.

Esta complejidad puede ser reducida, al precio de una disminución correspondiente de la rapidez del dispositivo, asociando no uno solo, sino varios niveles consecutivos del árbol a algunos por lo menos de cada uno de los controladores (o sea m< n). El número de niveles por controlador no es obligatoriamente idéntico para todos los controladores. En particular, si el controlador asociado al nivel 0 por lo menos asegura además otras funciones en conexión con el entorno del árbol de selección, se podrá prever que ese controlador administre un número de niveles menor que

\hbox{los otros.}

En el caso en el que un controlador está asociado a varios niveles del árbol, la propagación de un mando según estos niveles es tratada secuencialmente por este controlador.

Como muestra la figura 6 en el caso de un controlador 21_{q,p} asociado a los niveles q a q+p-1 del árbol, solamente los registros 26_{q}, 26_{q+p} de intercara entre los niveles asociados a unos controladores diferentes constituyen unos registros pipeline para el funcionamiento en paralelo de los controladores sucesivos. Los otros registros 26_{q+1}, ... 26_{q+p-1} son accesibles solamente por el controlador 21_{q,p}. Pueden formar parte del circuito lógico que constituye este controlador 21_{q,p}, o también formar parte del módulo de memoria reservado a este controlador y que comprende los niveles q a q+p-1.

Se observará que es posible prescindir de los contadores diferenciales \Delta(i) en los niveles del árbol binario asociados al m-ésimo controlador. Suponiendo que este último controlador esté asociado a los p niveles n-p a n-1 (1\leqp<n-1). Cuando un mando de inserción A_{n,p}=01 es leído en el registro pipeline 26_{n,p}, el padre de donde proviene este mando es el nudo 1D_{n-p} identificado en este registro. Si, para cada uno de los 2^{n-p-1} padres posibles, el último controlador mantiene al día una lista respectiva de hojas libres que forman parte de la descendencia de este nudo padre, entonces el último controlador puede tratar el mando de inserción propagándolo secuencialmente desde el nivel n-1 en dirección al nivel n-p a partir de una hoja libre que pertenece a la lista asociada al nudo padre identificado en el campo D_{n-p} del registro pipeline. En cada una de estas listas, cada una de las hojas puede ser designada simplemente por p bits que, con los n-p-1 bits de la identificación D_{n-p}, identifican la hoja de manera no ambigua. Una forma simple de mantener esta lista consiste en organizarla en modo último en entrar-primero en salir (LIFO). El último controlador puede también propagar el mando de inserción desde el nivel n-p en dirección al nivel n-1 dado que los bits que designan una hoja libre a partir de un padre identificado pueden ser utilizados en cada nivel para orientar la propagación del mando de inserción.

En definitiva, el dispositivo de selección del tipo ilustrado por las figuras 2 a 6 puede ser realizado previendo solamente 2^{n-p-1}-1 contadores diferenciales \Delta(i) respectivamente asociados a los pares de nudos 2i y 2i+1 del árbol para i que va de 1 a 2^{n-p-1}-1.

Las figuras 7 a 11 ilustran otro modo de realización de un dispositivo de selección.

Para facilitar la explicación, se considera de nuevo el caso en el que cada controlador 21_{q} está asociado a un solo nivel q del árbol binario (m=n). Se comprenderá sin embargo que, como anteriormente, la arquitectura de este dispositivo de selección es fácilmente transponible al caso en que uno por lo menos de los controladores está asociado a varios niveles (m < n).

Contrariamente al ejemplo de realización anteriormente descrito, el de las figuras 7 a 11 no utiliza contadores diferenciales para propagar los mandos de inserción del vértice hacia las hojas del árbol. Cada módulo de memoria 20_{q} correspondiente a un nivel q del árbol comprende así los nudos 2^{q} a 2^{q+1}-1 y los emplazamientos 23 para recibir los bits de orientación F(2^{q-1}) a F(2^{q}-1), pero no emplazamientos 25 para recibir unos contadores diferenciales, como muestra la figura 7.

Cada registro de intercara 26_{q} comprende, además de los cuatro emplazamientos que contienen los parámetros A_{q}, B_{q}, C_{q} y D_{q} anteriormente definidos, un emplazamiento suplementario que recibe un bit E_{q} que designa, cuando tiene lugar la propagación de un mando de inserción desde un nudo 1D_{q} del nivel q-1, el nudo hijo del nivel q hacia el cual es propagado este mando. Así, si E_{q}=0, el mando de inserción es propagado hacia el hijo izquierdo 1D_{q}0, mientras que, si E_{q}=1, el mando de inserción es propagado hacia el hijo derecho 1D_{q}1.

En el registro 26_{q}, la identificación D_{q} del nudo padre y el bit E_{q} de designación del nudo hijo están constituidos por los q bits de peso más fuertes del contenido G_{q} de un campo de designación de hoja de n-1 bits. El contenido G_{q} de este campo de designación de hoja designa, cuando tiene lugar la propagación de un mando de inserción, una de las hojas libres del árbol binario en dirección de la cual es propagado este mando. La representación binaria de esta hoja libre es 1G_{q}. Dado que la hoja designada está libre, se tiene la seguridad de que el elemento insertado podrá encontrar su lugar sobre el trayecto que va del vértice del árbol a esta hoja libre designada, a condición de que ningún otro mando de inserción hacia esta misma hoja esté en curso de propagación corriente abajo del árbol binario.

Para cumplir esta condición, el campo de designación de hoja del registro 26_{1} de intercara entre los niveles 0 y 1 recibe su valor G_{1} del controlador 21_{n-1} asociado al último nivel del árbol. El controlador 21_{n-1} mantiene una primera lista de hojas libres, por ejemplo por medio de un registro con desplazamiento 30 tal como el esquematizado en la figura 8. Este registro contiene un número n' de emplazamientos de n-1 bits, y efectúa una operación de desplazamiento en cada período de mando \theta_{1}. Cualquier hoja en dirección de la cual un mando de inserción es susceptible de estar en curso de propagación en el árbol binario, forma parte de esta primera lista de n' hojas libres. En tanto que el mando A_{n-1} leído por el último controlador en el registro de intercara 26_{n-1} no es un mando de inserción (A_{n-1}\neq 01), el registro con desplazamiento 30 es cerrado de nuevo sobre sí mismo como muestra la figura 8, de manera que suministra la misma designación de hoja cada n' período \int\theta_{1}. Esta designación G_{1}, de la cual se sabe entonces que es diferente de cada una de las dos hojas hacia las cuales unos mandos de inserción son susceptibles de estar en curso de propagación en el árbol, es inscrita en el campo correspondiente del registro de intercara 26_{1}. Si, por el contrario, un mando de inserción A_{n-1}=01 llega al último nivel del árbol, entonces una nueva hoja libre P, extraída por el último controlador de una segunda lista de hojas libres de una manera que será explicada más adelante, es introducida en el registro con desplazamiento 30 y en el registro de intercara 26_{1}.

Para explicar este funcionamiento, la figura 9 toma de nuevo en una forma simplificada los cronogramas de la figura 5 en el caso en que el dispositivo trate consecutivamente unos mandos de inserción de nuevos elementos en el árbol. En esta figura 9, cada extremo de flecha designa un instante \alpha'_{q} de inicio del tratamiento del mando de inserción por un controlador 21_{q}. Así, en los instantes \alpha'_{0}, el controlador 21_{0} recibe los mandos y parámetros pertinentes A_{0}, B_{0}, C_{0} desde el entorno del dispositivo, y en los instantes \alpha'_{q} con q \geq 1, el controlador 21_{q} recibe los mandos y parámetros A_{q}, B_{q}, C_{q} y G_{q} en el registro 26_{q} e inicia los tratamientos correspondientes. En el ejemplo de organización temporal representado en la figura 9, cada mando de inserción para la cual el último controlador 21_{n-1} ha escrito la designación correspondiente G_{1} de una hoja libre en el registro 26_{1} llega a este último controlador en el registro 26_{n-1} al cabo de dos períodos \theta_{1}. En consecuencia, en este ejemplo, es suficiente tomar n'=2 emplazamientos en el registro con el desplazamiento 30.

En este mismo ejemplo (ver también figura 1), la figura 8 muestra los n'=2 hojas 9 y 13 (respectivamente designadas por 001 y 101 puesto que las representaciones binarias de los números 9 y 13 son 1001 y 1101) contenidas en la lista mantenida en el registro 30. La hoja 9 ha sido por tanto designada en el campo G_{1} cuando ha tenido lugar el penúltimo mando. Si este mando se refiere a la inserción de un nuevo elemento y llega a la hoja 9 (es decir A_{n-1}=01 en el período corriente del funcionamiento del último procesador), la hoja 9 es suprimida de la lista y el registro 30, y reemplazada por una nueva hoja (10, 11 ó 15 en el caso de la figura 1) designada por P. Si no, dicho penúltimo mando o bien no se refiere a una inserción, o bien se refiere a la inserción de un elemento de datos que ha encontrado su lugar corriente arriba del nivel n-1, de manera que la hoja 9 es mantenida en el registro 30 y de nuevo designada en el campo G_{1} para el próximo mando.

En la práctica, el número n' podrá siempre ser inferior al número n de niveles en el árbol binario. Dado que este modo de realización del dispositivo de selección implica que el árbol binario tenga en cada instante por lo menos n' hojas libres, el número máximo de elementos de datos que el dispositivo es capaz de seleccionar es reducido, con respecto al dispositivo anteriormente descrito, en una cantidad siempre inferior a 2n', de manera que la capacidad de selección del dispositivo no esté afectada de forma significativa cuando el número de niveles no es demasiado pequeño. Si por ejemplo el dispositivo comprende n=12 niveles con n'=4, puede seleccionar hasta N=4095 elementos en el caso de utilización de contadores diferenciales, y hasta N=4088 elementos en el caso de utilización de listas de hojas libres, no siendo la diferencia entre estos dos valores de N significativa.

Las figuras 10A y 10B, que deben completarse con la figura 4C, muestran un organigrama semejante al de las figuras 4A a 4C (las mismas referencias numéricas han sido empleadas para designar unas etapas semejantes), y detallan las operaciones efectuadas por un controlador 21_{q} del tipo representado en la figura 7, con q < n-1, cuando tiene lugar el tratamiento de un mando.

Con respecto al organigrama de las figuras 4A, 4B, 4C, el de las figura 10A, 10B y 4C ha sido simplificado por la supresión de todas las operaciones que se refieren a los contadores diferenciales. En las etapas 105 y 117 ejecutadas en el tratamiento de un mando de inserción, el conjunto del campo de designación de hoja G_{q} o G_{q+1} es leído o escrito en el registro de intercara 26_{q} ó 26_{q+1}, y no solamente la identificación del nudo padre D_{q} o D_{q+1}. Con respecto al ejemplo anterior, se obtiene una simplificación de la estructura de los controladores y una reducción del espacio de memoria al cual cada uno de ellos debe respectivamente ser capaz de acceder.

Las figuras 11A y 11B, que deben completarse con la figura 4C, muestran las operaciones efectuadas por el último controlador con respecto al nivel n-1 del árbol. La etapa 150, 151 ó 152, ejecutada entre los instantes \beta_{n-1} y \alpha_{n-1} corresponde a la escritura, en el campo de designación de hoja del registro 26_{1}, de los n-1 bits de peso más bajos G_{1}=T(i) del número de la hoja de rango i (0 \leqi <n') en la lista de hojas libres que corresponden al contenido del registro con desplazamiento 30 ilustrado en la figura 8. El tratamiento de cada uno de los mandos con respecto al último nivel n-1 termina en todos los casos por un incremento, módulo n', del contador i en la etapa 153, lo que corresponde a una operación de desplazamiento en el registro 30.

El controlador 21_{n-1} mantiene además una segunda lista de hojas libres, que administra, por ejemplo en modo último en entrar-primero en salir (LIFO). La primera hoja de esta segunda lista está designada por un apuntador P de n-1 bits almacenado en un registro del último controlador o en su zona de memoria 20_{n-1}. La representación binaria del número de esta primera hoja es 1P. Cada hoja de la segunda lista contiene un elemento de datos cuya clave de selección es infinita, y se utiliza por ejemplo la porción de memoria correspondiente a la referencia asociada para almacenar un apuntador de seguimiento igual a la designación en n-1 bits de la hoja siguiente de la segunda lista (se podría también utilizar la porción correspondiente a la clave si se reserva un bit para identificar las claves infinitas).

Cuando un mando de inserción llega al controlador del último nivel en el registro de intercara 26_{n-1} (A_{n-1}=01), la hoja libre designada por G_{n-1} debe ser llenada para contener el nuevo elemento de datos. En consecuencia, las etapas 110 a 117 del organigrama de las figuras 10A y 10B no son necesarias. La etapa de lectura 105 es seguida por una etapa 155 en la que el controlador 21_{n-1} lee en la variable h el apuntador de seguimiento R(1P) contenido en la porción de memoria correspondiente a la referencia del elemento contenido en la primera hoja libre de la segunda lista (etapa 155). En la etapa siguiente 156, el controlador 26_{n-1} actualiza las dos listas de hojas libres. Retira de la primera lista la hoja libre designada por G_{n1}, reemplazándola, en la zona T(i) por el apuntador P de la primera hoja de la segunda lista; reemplaza a continuación este valor P por el del apuntador leído en la etapa 155. El procesador 21_{n-1} termina de tratar el mando de inserción procediendo a la etapa 150 citada y después a las etapas 119 a 126 de la figura 4C y a la etapa 153.

Para tratar un mando de intercambio (A_{n-1}=11), el controlador del último nivel ejecuta en principio las etapas 130 a 136 anteriormente comentadas. La etapa 137 no es necesaria, y es reemplazada por la etapa 151 citada. Si la clave de selección k=B_{n-1} propuesta en el intercambio desde el nivel n-2 es mayor que la K(1st) leída en la hoja tratada (v'=11 cuando tiene lugar la comparación 138), esta clave k es comparada con el infinito en la etapa 139. Si esta clave k es finita, el tratamiento del mando de intercambio termina por las etapas 119 a 126 de la figura 4C y por la etapa 153. Si no, el mando se refiere a una extracción simple, y libera una hoja anteriormente ocupada. En la etapa 157, esta hoja es actualizada escribiendo en la misma una clave de selección infinita y, a título de referencia, el valor P del apuntador de la primera hoja de la segunda lista. El bit de orientación asociado F(1s) recibe el valor complementario del leído en la etapa 131. Antes de pasar a la etapa final 153, el controlador 26_{n-1} termina el tratamiento del mando de extracción de la etapa 158 actualizando el apuntador P de la primera hoja de la segunda lista con la designación binaria st de la hoja liberada.

A la inicialización del dispositivo según las figuras 7 a 11, las dos listas de hojas libres son por ejemplo inicializadas de la manera siguiente: T(i)=i, en base 2, para 0 \leq i \leq n'; P=n', en base 2; y R(1i)=i+1, en base 2, para n' \leq i \leq 2^{n-1}.

En el ejemplo de instalación ilustrado por las figuras 8, 11A y 11B, el último controlador 21_{n-1} mantiene la "primera lista" y la "segunda lista" por medio de un registro con desplazamiento 30 y de una pila LIFO. Se observará que otras organizaciones lógicas de complejidad comparable podrían ser adoptadas. Por ejemplo, el controlador 21_{n-1} podría mantener una fila de espera lógica administrada en modo primero en entrar-primero en salir (FIFO), que contiene los números de las hojas libres, asegurándose de que esta fila de espera FIFO contiene siempre por lo menos n' números de hojas libres. En estas condiciones, la "primera lista" está constituida por los n' últimos emplazamientos de la fila de espera, y la "segunda lista" por los emplazamientos precedentes de la fila de espera.

En los dispositivos de selección descritos anteriormente, la relación de orden según la cual las claves son seleccionadas, es decir comparadas entre ellas en las etapas 111, 122, 123 y 133, corresponde al orden creciente de los enteros naturales. Se comprenderá que cualquiera que sea la relación de orden para la cual unas comparaciones son fácilmente realizadas por medio de circuitos lógicos simples podría ser utilizada para seleccionar los elementos en un dispositivo de este tipo.

Si, por ejemplo, cada clave de selección K(i) es una etiqueta temporal que define un instante futuro en el que se tendrá necesidad de ir a buscar la referencia correspondiente R(i) del elemento de datos, el dispositivo de selección puede servir de dispositivo de temporización para controlar el ordenamiento temporal del proceso. La clave del elemento situado en el vértice del árbol es entonces comparada en el instante corriente para intercambiar o extraer este elemento si el instante corriente es alcanzado.

Si, en esta aplicación, los valores de tiempo están codificados sobre L bits por un contador cíclico que varía de 0 a 2^{L}-1, la relación de orden entre dos claves k y k' de L bits puede ser: ksk' si y solamente si 0 \leq(k'-k)(mod 2^{L}) < 2^{L-1}. En otros términos, es suficiente, en la etapa 122, por ejemplo, calcular la diferencia k'-k sobre L bits (es decir ignorando la consideración de peso más fuerte), y examinar si el bit de peso 2^{L-1} de esta diferencia es 0 (k \leq k') o 1 (k > k'). El orden cronológico de las claves es entonces respetado siempre que ninguna clave designe un instante anterior de más de 2^{L-1} o posterior de más de 2^{L-1}-1 en el instante corriente, una condición fácil de cumplir por la elección de un número L suficientemente grande.

Se describirá ahora una aplicación de los dispositivos de selección descritos anteriormente en un espaciador de células ATM.

Las células ATM son unos paquetes de informaciones de 53 octetos transmitidos sobre unos enlaces físicos a gran velocidad (caudal de 155 ó 622 Mbit/s). Cada enlace físico soporta un múltiplex de células que pertenecen a diversas conexiones virtuales. La conexión virtual de la que sale cada célula es identificada por un par de identificadores VPI-VCI contenidos en el encabezamiento de la célula. Algunos equipos diferencian las conexiones virtuales según el identificador de conducto virtual (VPI: "Virtual Path Identifier"), mientras que otros equipos diferencian las conexiones virtuales sobre la base de los identificadores de vía virtual (VCI: "Virtual Channel Identifier"), o de los dos identificadores VPI, VCI.

En la presente descripción, se considerará que cada célula ATM destaca de una conexión virtual identificada por una identidad IdCx interna del equipo provisto del espaciador. Esta identidad interna puede corresponder al VPI, al VCI, al par VPI-VCI, o también, más cómodamente a una identidad específica propia del equipo y que comprende un menor número de bits que el VPI-VCI, de manera que facilite los accesos a unos módulos de memoria de tamaño razonable. Una forma apropiada de asociar dichas identidades IdCx a las células ATM se describe en la solicitud de patente francesa nº 97 01222.

El espaciador ATM es una unidad cuya función principal es regularizar el caudal de células sobre las diferentes conexiones soportadas por una conexión física. En general, cada fuente que emite sobre una conexión virtual negocia con el operador un caudal-cresta. Si este caudal-cresta no es respetado por la fuente, corre el riesgo de producirse unas congestiones en la red, y el operador está habilitado para destruir unas células sobre la conexión.

En un espaciador, un intervalo de separación T es asignado a cada conexión IdCx, de manera que dos células consecutivas relativas a la misma conexión virtual estén generalmente separadas de por lo menos el intervalo de tiempo T que corresponde típicamente a la inversa del caudal-cresta. Se habla entonces de espaciador real. El espaciador real calcula para cada célula una hora de emisión teórica TET, después almacena la célula en memoria para emitirla solamente en tiempo deseado. El intervalo de espaciado T es entonces respetado para todas las conexiones. En un espaciador llamado virtual, se calcula en primer lugar para cada célula una hora de emisión teórica TET, según los mismos procedimientos que anteriormente, después la célula es almacenada en memoria. La diferencia con el espacio real es que el espaciador virtual emite inmediatamente unas células en el orden de las horas de emisión teóricas. El espaciador virtual no degrada la fluctuación de los retardos de célula (CDV: "Cell Delay Variation"). Sin embargo, no reduce la degradación posible del caudal por unas filas de espera situadas corriente arriba del espaciador.

La función de espaciado es frecuentemente asociada a la función de policía que consiste en eliminar unas células transmitidas según una conexión virtual a un caudal superior al caudal-cresta, cuando este acceso de caudal es tal que ya no es posible producir un múltiplex de salida en el cual las células que sobresalen de la conexión están correctamente espaciadas sin que el CDV sobrepase un valor límite que depende de la calidad de servicio negociada con el operador. La función de policía interviene habitualmente en la forma de calcular las horas teóricas de emisión TET de las células.

Una forma clásica de asignar unas horas teóricas de admisión a las células y de asegurar la función de policía es aplicar el algoritmo GCRA ("Generic Cell Rate Algorithm") definido en el anexo 1 de la Recomendación I.371 del ITU-T (véase M. DE PRYCKER: "Asynchronous Transfer Mode, Solution for Broadband ISDN" 2ª edición, 1993, Capítulo 7, párrafo 7.3.4, páginas 292-293). Para cada conexión virtual, este algoritmo verifica siempre la relación siguiente: ta\leqTET\leqta+\tau, en la cual ta designa la hora de llegada de la célula, en la cual es calculada su hora teórica de emisión TET, y \tau designa la tolerancia de CDV de la conexión.

En el espaciador de la figura 12, la función de policía está asegurada por un módulo 40 sobre la base de la hora corriente y de la identidad IdCx de la conexión de la cual sobresale cada célula entrante. Este módulo 40 suministra al controlador de espaciado 41 la hora teórica de emisión TET calculada de forma recursiva para cada célula así como el intervalo de espaciado T asociado a la conexión de la que destaca esta célula. Sobre la base de estas informaciones y de las identidades de conexión IdCx, el controlador de espaciado 41 supervisa la gestión de la memoria de células 42 en la cual las células entrantes son escritas y las células salientes son leídas, y administra además una memoria de apuntadores 43 y el dispositivo de selección 44.

Se designa por NCX el número de conexiones virtuales, numeradas de IdCx=1 a IdCx=NCX, que el espaciador es capaz de tratar, y por NCE el número de células que la memoria 42 es capaz de contener, en unos emplazamientos previamente definidos Ch_cell(1) a Ch_cell(NCE).

En el ejemplo de realización representado, la memoria de células 42 y la memoria de apuntadores 43 consisten en dos módulos de memorias distintos, de los cuales el primero está administrado por la unidad 46 bajo el control del controlador 41. Se comprenderá sin embargo que otras formas de realización son posibles. En particular, las memorias 42 y 43 podrían estar montadas en un solo módulo de memoria en el cual los accesos serían mandados por el controlador 41. Así, un módulo de memoria RAM de 2 megaoctetos permite por ejemplo almacenar hasta NCE=32.000 células que sobresalen de NCX=4 096 conexiones virtuales diferentes así como los apuntadores necesarios para la gestión de la memoria de células.

La figura 13 muestra una señal de reloj-célula CKC sobre la base del cual un secuenciador 47 del espaciador proporciona las señales de cadenciado necesarias al módulo 40, al controlador de espaciado 41, al dispositivo de selección 44 y al gestor 46 de la memoria de células (figura 12). El período de esta señal de reloj es de 2,7 \mus en el caso de una conexión con 150 Mbit/s. En cada período de esta señal CKC, el espaciador debe ser capaz de recibir una célula escrita en la memoria 42 (tercera línea de la figura 13), y de emitir una célula leída en la memoria 42 (cuarta línea de la figura 13). En el ejemplo de cadenciado representado en la figura 13, cada período de célula está dividido en dos fases sucesivas de igual duración, la primera para la recepción eventual de una célula entrante y la segunda para la emisión eventual de una célula saliente.

En la primera fase de cada período de célula, el controlador de espaciado 41 proporciona al gestor 46 una dirección de salida a en la memoria de células 42, a partir de la cual éste manda la escritura de los 53 octetos de la célula entrante. En la segunda fase, la dirección de salida a proporcionada por el controlador 41 sirve al gestor 46 para mandar la lectura de los 53 octetos almacenados a partir de la dirección a de la memoria 42 a fin de suministrar la célula saliente. En la presente exposición, se considerará que la dirección a corresponde al número del emplazamiento Ch_cell(a) de la memoria 42(1\leqa\leqNCE) en la cual la célula es escrita o leída, y que, por convención, a=0 informa al gestor 46 que no debe mandar acceso a la memoria 42 en la fase considerada (sin célula entrante, o ninguna célula a emitir, en el curso del período de célula).

La memoria de células 42 están organizada de manera que contenga, para cada conexión virtual para la cual contiene unas células, una lista de emplazamientos donde estas células están ordenadas en modo primero en entrar-primero en salir (FIFO). Estas listas son administradas por el controlador 41 por medio de la memoria de apuntadores 43.

Los apuntadores de la memoria 43 comprenden un apuntador de emplazamiento libre Ptr_libre, NCX apuntadores de cabeza de lista Ptr_cabeza (IdCx) para 1\leqIdCx\leqNCX, NCX apuntadores de final de lista Ptr_fin(IdCx) para 1<IdCx\leqNCX, y NCE apuntadores de continuación Ptr_continuación(i) para 1\leqi\leqNCE, respectivamente asociados a los emplazamientos Ch_cell(1) a Ch_cell(NCE). Cada identidad IdCx de una conexión virtual para la cual la memoria 42 no contiene ninguna célula en un instante dado tiene su apuntador de final de lista Ptr_fin(IdCx) a cero en ese instante, que indica una lista vacía (es el caso para IdCx=2 en el ejemplo representado en la figura 12). Si no, el número i del emplazamiento Ch_cell(i) donde esta almacenada la célula recibida desde el tiempo más largo sobre la conexión IdCx es igual al apuntador de cabeza de lista Ptr_cabeza(IdCx), y el número de aquel donde está almacenada la célula recibida desde el tiempo menos largo según la conexión IdCx es igual al apuntador de final de lista Ptr_fin(IdCx). La lista FIFO relativa a una conexión IdCx está encadenada por medio de los apuntadores de continuación: el apuntador de continuación Ptr_continuación(i) asociado a un emplazamiento Ch_cell(i) que no es un final de lista designa el emplazamiento Ch_cell(Ptr_continuación)) que le sigue en su lista. Si el emplazamiento Ch_cell(i) es un final de lista, entonces se impone Ptr_continuación(i)=0. En el ejemplo de la figura 12, la lista relativa a IdCx=1 es Ch_cell(NCE-1), Ch_cell(1) y Ch_cell(3), y la relativa a IdCx=NCX se reduce al emplazamiento Ch_cell(6). Los emplazamientos de la memoria 42 que no están ocupados por unas células a emitir forman una lista LIFO de emplazamientos libres, de los que el primero está designado por el apuntador Ptr_libre y los siguientes por los apuntadores de continuación sucesivos. En el ejemplo de la figura 12, la lista de emplazamientos libres es, en el orden de salida, Ch_cell(5), Ch_cell(NCE) y Ch_cell(2).

El vértice del árbol de selección del espaciador de la figura 12 es accesible por el controlador de espaciado 41, que asegura los tratamientos del controlador 21_{0} asociado al nivel 0 (figuras 2 a 11). El elemento de datos K(1), R(1) situado en el vértice del árbol puede entonces ser almacenado en la memoria de apuntadores 43 como se ha representado, o también en un registro especial del controlador 41. El controlador 41 intercambia los mandos y parámetros con los niveles 1 a n-1 del dispositivo de selección 44 por medio del registro de intercara 26_{1} que, en el ejemplo considerado, está de acuerdo con el descrito con referencia a la figura 7.

Cada elemento de datos proporcionado al dispositivo de selección 44 consiste, para la clave de selección K(i), en la hora teórica de emisión de una célula almacenada en un emplazamiento de la memoria 42 que constituye una cabeza de lista, y para la referencia R(i), en la identidad IdCx de la conexión virtual de la cual sobresale esta célula. La clave K(i) es por tanto una etiqueta temporal que puede ser definida, como se ha explicado anteriormente, por un contador cíclico de L bits. Un contador L=16 bits por ejemplo, más un bit para distinguir las claves infinitas, conviene para la aplicación a un espaciador ATM. Las referencias R(i) pueden ser sobre 12 bits para NCX=4096 conexiones.

Si el espaciador es un espaciador real, el controlador 41 compara la clave K(1) presente en el vértice del árbol con el instante corriente ta, y proporciona a=Ptr_cabeza(R(1)) al gestor 46 si K(1) \leq ta para que sea emitida la célula que, entre las situadas en las cabezas de lista, tiene la hora teórica de emisión más pequeña. En el caso de un espaciador virtual, el controlador 41 actúa de la misma manera, pero sin comparación con el instante corriente: una célula es emitida en cada período desde que K (1) < \infty .

A la llegada de una célula que sale de una conexión IdCx cuya lista de emplazamientos está vacía (Ptr_fin(IdCx)=0), esta célula es almacenada en el emplazamiento Ch_cell(Ptr_libre), la lista de los emplazamientos libres es actualizada, y el controlador 41 manda la inserción en el árbol de selección de un elemento de datos cuya referencia corresponde a esta IdCx y cuya clave de selección es el TET calculado por el módulo 40 para esta célula.

La llegada de una célula que sale de una conexión IdCx cuya lista de emplazamientos no está vacía no modifica el contenido del árbol de selección, y necesita solamente un almacenado en el emplazamiento Ch_cell(Ptr_libre) y una actualización de la lista de los emplazamientos libres y de la lista asociada a la conexión IdCx.

La emisión de una célula que sale de una conexión IdCx cuya lista de emplazamientos contiene esta sola célula provoca la extracción simple del elemento correspondiente del árbol de selección, que vuelve a un intercambio con un elemento de clave infinita.

La emisión de la célula que sale de una conexión IdCx cuya lista de emplazamientos contiene una o varias células después de ésta provoca el intercambio entre el elemento correspondiente del árbol y un nuevo elemento cuya referencia corresponde a este IdCx y cuya clave de selección es el tiempo teórico de emisión asignado a la célula almacenada en segunda posición en la lista, es decir en un emplazamiento Ch_cell(Ptr_continuación(Ptr_cabeza(IdCx))).

En este último caso, la hora teórica de emisión que constituye la clave del nuevo elemento puede ser la proporcionada por el módulo 40 para la célula almacenada en la nueva cabeza de lista. Es entonces útil memorizar las horas TET proporcionadas por el módulo 40 a medida que tiene lugar la llegada de las células. Pero, es preferible que el controlador 41 calcule de nuevo una hora teórica de emisión de la célula en el momento en que proporciona el nuevo elemento de datos al dispositivo de selección 44.

A este fin, la memoria 43 contiene una tabla en la cual están almacenados los valores TT(IdCx) de los intervalos de espaciado T asignados a las diferentes conexiones virtuales IdCx, valores que el controlador 41 recibe del módulo 40 en los momentos en que unas células llegan según las conexiones interesadas. Cuando K(1)\leqta, el espaciador real emite la célula almacenada en Ch_cell(Ptr_cabeza(R(1))), y manda en el árbol de selección un intercambio del elemento K(1), R(1) situado en el vértice con un nuevo elemento K(1)+TT(R(1)), R(1). En otros términos, la hora teórica de emisión de la célula almacenada en la nueva cabeza de lista es tomada igual a la de la célula emitida aumentada en el intervalo de tiempo TT (IdCx) asignado a la conexión interesada.

Esta forma de proceder presenta dos ventajas. La primera es que si el módulo 40 afecta a dos células consecutivas que salen de una conexión IdCx de las horas teóricas de emisión TET distantes de más de TT (IdCx) en razón de sus horas de llegada respectivas y si la segunda de estas dos células está ya escrita en la memoria 42 en el momento en que la primera es emitida, entonces se puede avanzar la hora teórica de emisión de la segunda célula con respecto a la calculada por el módulo 40 así como las horas teóricas de emisión de células siguientes de la conexión sin perjudicar las propiedades del espaciador requeridas. Se evita por tanto retardar inútilmente algunas células.

La segunda ventaja es que se puede modificar dinámicamente y de forma inmediata los intervalos de espaciado asignados a algunas conexiones. Cuando el volumen de la conexión corre el riesgo de provocar una congestión, el equipo puede por ejemplo aumentar el intervalo de espaciado de ciertas conexiones virtuales. Este aumento surte efecto inmediatamente, incluso para las células de esta conexión contenidas en la memoria 42 que no serán por tanto emitidas de acuerdo con sus TET inicialmente calculados. Se evita así un retardo en aplicación de las medidas preventivas, retardo que podría conducir a que la congestión no sea evitada. Desde luego, la autorización de aumentar el intervalo de espaciado de una conexión debe ser convenido con la fuente para el establecimiento de esta conexión dado que, para una misma tolerancia de CDV y un mismo comportamiento de la fuente, aumenta la probabilidad de destrucción de células para la función de policía.

La figura 14 muestra las operaciones efectuadas por el controlador 41 en la primera fase de cada período de célula, durante los intervalos de tiempo 200 indicados por la segunda línea de la figura 13.

La primera etapa 201 consiste en determinar si una célula entrante llega al espaciador durante el período de célula en cuestión, y en caso necesario en adquirir la identidad IdCx de la conexión de la cual sale esta célula así como la hora teórica de emisión TET y el intervalo de espaciado T proporcionado para esta célula por el módulo 40.

En ausencia de recepción de una célula entrante, la dirección a=0 es proporcionada al gestor 46 de la memoria de células en la etapa 202, y después el controlador 41 escribe en el registro de intercara 26_{1} un mando de ausencia de modificación del contenido del árbol binario (A_{1}=00) en la etapa 203.

En presencia de una célula entrante, el apuntador de emplazamiento libre Ptr_libre es leído en la memoria de apuntadores 43 en la etapa 204, y asignado a la dirección a que es proporcionada al gestor 46 en la etapa 202. Si a=0 (sin célula recibida o ningún emplazamiento libre en la memoria 42), el gestor 46 no procede a ninguna escritura en la memoria 42 en el período de célula corriente, y el controlador de espaciado 41 ejecuta la etapa 203 citada para que el contenido del árbol binario permanezca invariable. Si no, el controlador 41 pasa a la etapa 205 de lectura de apuntadores.

En la etapa 205, el número Ptr_continuación(a) del segundo emplazamiento de la lista de emplazamientos libres, el número Ptr_cabeza(IdCx) de la cabeza de lista relativa a la conexión IdCx y el apuntador Ptr_fin(IdCx) de esta lista son respectivamente asignados a las variables b, c y d. En la etapa 206, la tabla TT de los intervalos de espaciado es actualizada para la conexión IdCx según el valor T recibido del módulo 40, la dirección a es escrita en la memoria 43 como apuntador de final de lista de emplazamientos relativa a la conexión IdCx, el apuntador de continuación Ptr_continuación (a) asociado a este emplazamiento es puesto a cero para indicar que se trata por otra parte de un final de lista, y el apuntador de emplazamiento libre Ptr_libre es actualizado con la variable b.

Si la lista de emplazamientos relativa a la conexión IdCx no estuviera vacía (es decir, si d \neq 0 cuando tiene lugar la comparación 207), ninguna modificación del contenido del árbol de selección es necesaria como se ha explicado anteriormente, de manera que el controlador de espaciado 41 ejecuta la etapa 203 citada después de haber actualizado el apuntador de continuación asociado al precedente final de lista con el antiguo apuntador del emplazamiento libre en la etapa 208: Ptr_continuación(d)=a.

Si la comparación 207 muestra que d=0, el controlador 41 acaba la actualización de los apuntadores de lista en la etapa 209 escribiendo Ptr_cabeza(IdCx)=a. Procede a continuación a la inserción del nuevo elemento de datos TET, IdCx en el árbol de selección. Las operaciones que efectúa para ello corresponden a las efectuadas por el controlador 26_{0} del nivel 0 del árbol binario, es decir a las etapas 110 a 119 del organigrama de las figuras 10A, 10B y 4C. En la etapa 210, el controlador 41 asigna a las variables k y r la clave de selección K(1) y la referencia R(1) del elemento de datos leído en el vértice del árbol, y después compara la clave k con la hora teórica de emisión TET recibida del módulo 40 en la etapa 201 (comparación 211). Si TET\geqk, el mando de inserción debe ser propagado hacia el nivel 1 del árbol de selección, de manera que el controlador 41 escribe A_{1}=01, B_{1}=TET y C_{1} = IdCx en el registro pipeline 26_{1} en la etapa 212, recibiendo el campo de designación de hoja del registro 26_{1} el número de una hoja libre G_{1} desde el último controlador 21_{n-1} del dispositivo de selección 44, como se ha indicado en la figura 12.

Si la comparación 211 muestra que TET<k, entonces el nuevo elemento de dato TET, IdCx debe escribirse en el vértice del árbol, lo que es efectuado en la etapa 216. Previamente, el controlador 41 propaga un mando de reinicialización A_{1}=10 en el registro pipeline 26_{1} en la etapa 214 si la clave de selección k anteriormente situada en el vértice del árbol es infinita (comparación 213). Si no, el controlador 41 escribe en el registro 26_{1} un mando de inserción (A_{1}=01) del elemento B_{1}=k, C_{1}=r anteriormente situado en el vértice en la etapa 215.

En lo que concierne a la sincronización del controlador 41 con los del dispositivo de selección 44, la figura 14 muestra que el instante \alpha_{0} correspondiente a aquél del cual se ha tratado con referencia a las figuras 5 y 9, se encuentra después de la etapa 203, 212, 214 ó 215 de escritura por el controlador 41 en el registro pipeline 26_{1}. A partir de este instante \alpha_{0}, el controlador 21_{1} del nivel 1 puede empezar a tratar el mando (instante \alpha'_{1} indicado en la
figura 13).

La figura 15 muestra las operaciones efectuadas por el controlador 41 en la segunda fase de cada período de célula, durante los intervalos de tiempo 300 indicados en la segunda línea de la figura 13.

La primera etapa 301 consiste en leer la clave de selección K(1) y la referencia R(1) del elemento de datos situado en el vértice del árbol y en asignarla respectivamente a las variables k y r. La comparación siguiente 302 sirve para decidir si una célula debe emitirse o no. En el caso de un espaciador real, esta etapa 302 consiste en comparar la clave de selección k con la hora corriente ta. En el caso de un espaciador virtual, la misma consiste simplemente en examinar si la clave k es finita o infinita. Si k > ta (caso de un espacio real), el controlador 41 no efectúa ninguna operación en la segunda fase del período de célula, salvo la escritura en el registro pipeline 26_{1} de un mando A_{1} =00 de ausencia de modificación del contenido del árbol binario (etapa 303).

Si resulta de la etapa 302 que una célula debe emitirse, el número del emplazamiento situado en cabeza de lista relativamente a la conexión r, así como el apuntador de continuación asociado a este emplazamiento son leídos en la memoria 43 y respectivamente asignados a las variables a y b en la etapa 304. La dirección a puede entonces ser proporcionada al gestor 46 en la etapa 305 para que éste emita la célula almacenada a esta dirección (cuarta línea de la figura 13). Si la lista de emplazamientos relativa a la conexión r=R(1) identificada en el elemento situado en el vértice del árbol sólo contenía una célula, entonces la variable b está a 0. Esto es detectado por la comparación 306. En este caso, el apuntador de final de lista Ptr_fin(r) es puesto a cero en la etapa 307 para indicar que esta lista no contenía ninguna célula, y en la etapa 308 un valor infinito es asignado a la hora teórica de emisión TET que constituirá la clave de selección de un nuevo elemento a intercambiar en el árbol binario.

Si b \neq 0 en la etapa 306, la lista de emplazamientos contiene varias células, y la variable b es escrita en la etapa 309 como apuntador de cabeza de está lista, y, en la etapa 311, la célula almacenada en el emplazamiento Ch_cell(b) recibe una nueva hora teórica de emisión TET igual a la clave k=K(1) leída en la etapa 301, aumentada en una variable T tomada igual al intervalo de espaciado TT(r) de la conexión interesada, leída en la etapa 310. El mando de intercambio (A_{1}=11) del elemento K(1), R(1) situado en el vértice del árbol con el nuevo elemento B_{1}=TET, C_{1}=r se escribe en el registro pipeline 26_{1}en la etapa 312.

El instante \alpha_{0} a partir del cual el controlador 21_{1} del dispositivo de selección 44 puede empezar a tratar el mando se sitúa después de la etapa 312 (o la etapa 303), como muestra la figura 15. El controlador de espaciado 41 debe esperar el instante \beta_{0}'\geq \beta_{1}(ver figura 13) antes de recuperar en el registro 26_{1} el elemento devuelto desde el nivel 1 del árbol de selección. En el ejemplo ilustrado por la figura 15, el controlador 41 actualiza la lista de emplazamientos libres en el intervalo [\alpha_{0}, \beta'_{0}]: en la etapa 313, lee el apuntador de emplazamiento libre Ptr_libre y lo asigna a la variable c; después, en la etapa 314, escribe en la memoria 43 Ptr_continuación(a)=c y Ptr_libre=a.

Una vez que el controlador del nivel 1 del árbol ha devuelto el elemento que tiene la menor clave en el registro 26_{1}, este elemento es leído por el controlador 41 en la etapa 315, y después escrito en el vértice del árbol en la etapa 316.

La figura 16 muestra una variante de espaciador de células ATM capaz de tener en cuenta el índice de prioridad asignado a las conexiones virtuales. Se anota u este índice de prioridad, del cual se supone que tomas sus valores entre 1 y U. El espaciador de la figura 16 comprende U dispositivos de selección 44^{(u)} que tienen cada uno un registro pipeline 26_{1}^{(u)} entre su nivel 0 y su nivel 1. El funcionamiento de cada dispositivo de selección 44^{(u)} es el mismo que el descrito anteriormente. El vértice de cada árbol binario se supone contenido en la memoria de apuntadores 43 (cuyo resto del contenido no está representado en la figura 16) y administrado por el controlador de espaciado 41. El funcionamiento de la memoria de células 42 y de su gestor 46 es el mismo que el anterior para la escritura y la lectura de las células en las direcciones a proporcionadas por el controlador 41.

Cada uno de los dispositivos de selección 44^{(u)} trata unos elementos de datos cuyas referencias R^{(u)}(i) designan unas identidades de conexiones virtuales IdCx que tienen el mismo índice de prioridad u. Entre estos elementos, el dispositivo 44^{(u)} selecciona en su vértice (en la memoria 43 en el ejemplo representado) un elemento cuya clave K^{(u)}(1) es mínima. El controlador de espaciado está entonces dispuesto para mandar la emisión de la célula contenida en la cabeza de lista relativa a la conexión identificada a aquél de los elementos de datos situados en unos vértices de los árboles que presenta la clave de selección menor. En caso de igualdad entre varias claves de selección mínimas K^{(u)}(1), el controlador de espaciado 41 retiene la conexión que tiene el índice de prioridad mayor entre los ex acquos.

Esta gestión de los índices de prioridad no complica de forma significativa el controlador de espaciado 41. En lo que concierne a las operaciones efectuadas en la recepción de la célula, el organigrama de la figura 14 es invariable, siendo las etapas 210 a 216 efectuadas con respecto al árbol de selección 44^{(u)} que corresponde al índice de prioridad u recibido por el controlador 41 al mismo tiempo que la identidad de la conexión IdCx.

En lo que concierne a las operaciones efectuadas en la segunda fase de cada período de célula (figura15), las etapas 301, 302 de lectura del elemento situado en el vértice del árbol y de comparación de la clave de este elemento con la hora corriente se efectúan sucesivamente en el orden decreciente de los índices de prioridad hasta que, para un índice u, la etapa 302 muestra que la hora corriente ha sido alcanzada. En este caso, las etapas 304 a 316 son ejecutadas sin cambios, siendo efectuadas la escritura 312 y la lectura 315 en el registro 26_{1}^{(u)}, y la escritura 316 en el vértice del árbol de selección interesado.

En el ejemplo de la figura 16, los U dispositivos de selección son distintos. Se observará que estos diferentes dispositivos de selección podrían compartir sus medios de control, a saber sus controladores 21_{q} y sus registros pipeline 26_{q} . La figura 17 ilustra dicha aplicación en el caso particular en que U=2.

En el modo de realización de la figura 17, los U=2 árboles de selección comparten los registros de intercara 26_{q} y los controladores de nivel 21_{q}. Solamente sus niveles de memorización 20_{q}^{(1)}, 20_{q}^{(2)} (q\geq0) están diferenciados. Las dos etapas 0 están comprendidas en la memoria de apuntadores 43. Para cada nivel q \geq 1, los niveles correspondientes 20_{q}^{(1)}, 20_{q}^{(2)} de los dos árboles están formados por dos zonas distintas de la memoria administrada por el controlador 21_{q}, diferenciadas sobre la base de un bit de dirección suplementario constituido por ejemplo por el índice binario de prioridad que forma entonces el bit de peso más fuerte del campo D_{q} de los registros pipeline.

Claims (17)

1. Dispositivo de selección de elementos de datos que incluyen cada uno una clave de selección respectiva, que comprende:

-

unos medios de memorización organizados según un árbol binario de 2^{n-}1 nudos numerados de 1 a 2^{n-}1 aptos para contener cada uno un elemento de datos y repartidos en n niveles sucesivos numerados de 0 a n-1, comprendiendo el nivel q los nudos 2^{q} a 2^{q+1}-1; y

-

unos medios de control del árbol binario para distribuir los elementos a seleccionar en el árbol de manera que verifiquen una condición de ordenamiento según la cual, para cada entero i comprendido entre 1 y 2^{n-1-}1 tal que el nudo i contenga un elemento a seleccionar, cada uno de los nudos 2i y 2i+1 o bien no contiene ningún elemento a seleccionar, o bien contiene un elemento cuya clave de selección es superior o igual, en el sentido de una relación de orden determinada, a la clave de selección del elemento contenido en el nudo i,

en el cual los medios de control responden a unos mandos de modificación del contenido del árbol binario que incluyen unos mandos de inserción de un nuevo elemento a seleccionar,

caracterizado porque los medios de control comprenden m controladores sucesivos (21_{q}) asociados cada uno a un nivel (20_{q}) o a varios niveles consecutivos del árbol binario, siendo m un entero comprendido entre 2 y n, y n-1 registros de intercara (26_{q}) entre niveles sucesivos, entre los cuales cada uno de los m-1 registros de intercara entre pares de niveles asociados a unos controladores diferentes constituye un registro pipeline, y porque cada mando de modificación del contenido del árbol binario es propagado del nivel 0 hacia el nivel n-1 por medio de los registros de intercara, permitiendo el o los registros pipeline un trabajo en paralelo de los controladores.

2. Dispositivo según la reivindicación 1, en el cual para cada entero q comprendido entre 1 y n-1, el registro (26_{q}) de intercara entre el nivel q-1 y el nivel q comprende un primer emplazamiento para recibir un mando (A_{q}) propagado de un nudo del nivel q-1 hacia un nudo del nivel q, un segundo emplazamiento para recibir una identificación (D_{q}) de dicho nudo del nivel q-1 al cual el controlador asociado (21_{q-1}) accede cuando tiene lugar el tratamiento de dicho mando, y un tercer emplazamiento para recibir un elemento de datos (B_{q}, C_{q}) transmitido desde o hacia dicho nudo del nivel q-1.

3. Dispositivo según la reivindicación 2, en el cual, para cada entero q comprendido entre 1 y n-1, el registro (26_{q}) de intercara entre el nivel q-1 y el nivel q comprende un cuarto emplazamiento para recibir un bit (E_{q}) que designa, con la identificación (D_{q}) contenida en el segundo emplazamiento, el nudo del nivel q hacia el cual es propagado dicho mando y al cual el controlador asociado (21_{q}) accede cuando tiene lugar el tratamiento del mando (A_{q}) contenido en el primer emplazamiento si éste se refiere a la inserción de un nuevo elemento en el árbol.

4. Dispositivo según la reivindicación 3, en el cual, para cada entero q comprendido entre 1 y n-1, los segundo y cuarto emplazamientos del registro (26_{q}) de intercara entre el nivel q-1 y el nivel q forman parte de un campo de designación de hoja de n-1 bits que contiene, cuando tiene lugar la propagación de un mando de inserción de nuevo elemento, los n-1 bits de peso más bajo del número de una hoja libre, es decir de un nudo libre del nivel n-1, en dirección al cual es propagado dicho mando, siendo el nudo del nivel q hacia el cual es propagado dicho mando designado por los q bits de peso más fuerte del contenido del campo de designación de hoja.

5. Dispositivo según la reivindicación 4, en el cual el controlador (21_{n-1}) asociado al nivel n-1 del árbol administra una primera lista de hojas libres que contiene un número determinado n' de hojas libres que incluye cada hoja en dirección a la cual un mando de inserción de nuevo elemento está en curso de propagación en el árbol, y una segunda lista de hojas libres que contiene las hojas libres no contenidas en la primera lista,

en el cual, cuando tiene lugar la inscripción de un mando de inserción del nuevo elemento a seleccionar en el primer emplazamiento del registro de intercara entre los niveles 0 y 1, los n-1 bits de peso más bajo del número de una hoja libre de la primera lista, diferente de cada hoja en dirección a la cual otro mando de inserción está en curso de propagación en el árbol, son inscritos en el campo de designación de hoja del registro de intercara entre los niveles 0 y 1,

en el cual, cuando tiene lugar la extracción de un elemento desde una hoja del árbol, esta hoja está incluida en la segunda lista de las hojas libres,

y en el cual, cuando un mando de inserción de un nuevo elemento llega al nivel n-1 en el registro de intercara (26_{n-1}) entre los niveles n-2 y n-1, el controlador asociado (21_{n-1}) extrae de la primera lista de hojas libres la hoja (G_{n-1}) designada por los n-1 bits del campo de designación de hoja de dicho registro de intercara, y la reemplaza por una hoja (P) de la segunda lista.

6. Dispositivo según la reivindicación 5, en el cual n'< n.

\newpage

7. Dispositivo según la reivindicación 5 ó 6, en el cual la primera lista de hojas libres está almacenada en un registro con desplazamiento (30) cerrado sobre sí mismo, que tiene n' emplazamientos que reciben cada uno los n-1 bits de peso más bajo de un número de hoja.

8. Dispositivo según la reivindicación 5, 6, ó 7, en el cual la segunda lista de hojas libres está almacenada en modo último en entrar-primero en salir en forma de una cadena de apuntadores, representando cada apuntador el número de una hoja, estando el primer apuntador (P) de la cadena almacenado en un emplazamiento específico, y estando el i-ésimo apuntador de la cadena (i \geq 2) almacenado en la hoja cuyo número está representado por el (i-1-ésimo) apuntador de la cadena.

9. Dispositivo según la reivindicación 5 ó 6, en el cual las primera y segunda listas son almacenadas en forma de una fila de espera lógica de tipo primero en entrar-primero en salir que tiene por lo menos n' emplazamientos, estando la primera lista constituida por los n' últimos emplazamientos de la fila de espera lógica y la segunda lista por los emplazamientos precedentes de la fila de espera lógica.

10. Dispositivo según la reivindicación 2 ó 3, en el cual, siendo p el número, superior o igual a 1 e inferior a n-1, de niveles del árbol binario asociado al m-ésimo controlador, los medios de memorización comprenden por lo menos 2^{n-p-1}-1 emplazamientos (25) para contener unos contadores diferenciales (\Delta(i)) respectivamente asociados a los pares de nudos 2i y 2i+1 del árbol para i que va de 1 a 2^{n-p-1}-1, teniendo cada contador diferencial asociado a un par de nudos un valor indicativo de la diferencia entre los números de elementos de datos respectivamente contenidos en los descendientes de los dos nudos de dicho par, estando los descendientes de un nudo i de un nivel q definidos como los 2^{n-q}-1 nudos del árbol binario cuyos números son de la forma i2^{j}+j donde j y j' son unos enteros tales que 0 \leq j < n-q y 0 \leq j'<2^{j},

y en el cual, cuando el registro de intercara (26_{q}) entre el nivel q-1 y el nivel q(1\leqq<n-p) recibe un mando de inserción (A_{q}) de un nuevo elemento en su primer emplazamiento y la identificación (D_{q}) de un nudo i del nivel q-1 en su segundo emplazamiento, dicho mando de inserción es propagado hacia el nudo 2i ó 2i+1 del nivel q según el valor del contador diferencial (\Delta(i)) asociado al par de nudos 2i y 2i+1.

11. Dispositivo según la reivindicación 10, en el cual los emplazamientos (25) de los medios de memorización que contienen los contadores diferenciales (\Delta(i)) asociados a los pares de nudos de un nivel son accesibles por el mismo controlador que los nudos de dicho nivel.

12. Dispositivo según cualquiera de las reivindicaciones 2 a 11, en el cual los medios de memorización comprenden 2^{n-1}-1 emplazamientos (23) para contener unos bits de orientación (F(i)) respectivamente asociados a los pares de nudos 2i y 2i+1 del árbol para i que va de 1 a 2^{n-1}-1, apuntando cada bit de orientación asociado a un par de nudos a uno de los nudos de dicho par que contiene un elemento cuya clave de selección es inferior o igual a la clave de selección del elemento contenido en el otro nudo de dicho par,

y en el cual, cuando el registro de intercara (26_{q}) entre el nivel q-1 y el nivel q(1\leqq\leqn-1) recibe un mando (A_{q}) de extracción o de intercambio de un elemento en su primer emplazamiento y la identificación (D_{q}) de un nudo i del nivel q-1 en su segundo emplazamiento, dicho mando de extracción o de intercambio es propagado hacia el nudo 2i ó 2i+1 del nivel q según el valor del bit de orientación (F(i)) asociado al par de nudos 2i y 2i+1.

13. Dispositivo según la reivindicación 12, en el cual los emplazamientos (23) de los medios de memorización que contienen los bits de orientación (F(i)) asociados a los pares de nudos de un nivel son accesibles por el mismo controlador que los nudos de dicho nivel.

14. Espaciador de células ATM transmitidas según un conjunto de conexiones virtuales, que comprenden una memoria de células (42) en la cual una células entrantes son escritas y unas células salientes son leídas, y unos medios (40, 41) para atribuir una hora teórica de emisión (TET) a cada célula almacenada en la memoria de células, caracterizado porque comprende además unos medios de control de espaciado (41, 46) para administrar la memoria de células (42), con la ayuda de una memoria de apuntadores asociada (43), de manera que la memoria de células comprende, para cada conexión virtual para la cual contiene unas células, una lista de emplazamientos en la que estas células están ordenadas en modo primero en entrar-primero en salir entre una cabeza de lista y un final de lista, y unos medios de selección (41, 44) para ordenar unos elementos de datos (K(i), R(i)) que comprenden cada uno una identidad de conexión virtual y una clave de selección que consiste en la hora teórica de emisión de la célula contenida en la cabeza de lista relativa a dicha conexión virtual, y para seleccionar por lo menos un elemento de datos que tiene una clave de selección mínima, porque los medios de control de espaciado están dispuestos para comprender la emisión de una célula contenida en la cabeza de lista relativa a una conexión virtual identificada en un elemento de datos seleccionado por los medios de selección, y porque los medios de selección comprenden por lo menos un dispositivo de selección según cualquiera de las reivindicaciones 1 a 13, cuyo nudo 1 del nivel 0 contiene dicho elemento seleccionado.

15. Espaciador según la reivindicación 14, en el cual los medios para atribuir una hora teórica de emisión a cada célula almacenada en la memoria de células comprenden unos medios (40) de cálculo recursivo de una hora teórica de emisión (TET) para cada célula que sale de una conexión virtual sobre la base de parámetros que incluyen por lo menos la hora de llegada (ta) de dicha célula y un intervalo de espaciado (T) asignado a dicha conexión,

en el cual, con la llegada de una célula que sale de una conexión virtual para la cual la memoria de células (42) no contiene ninguna célula, los medios de selección (41, 44) reciben un nuevo elemento de datos que comprende la identidad de dicha conexión virtual y, como clave de selección, la hora teórica de emisión de dicha célula proporcionada por los medios (40) de cálculo recursivo,

y en el cual, con la emisión de una primera célula que sale de una conexión virtual para la cual la memoria de células comprende una lista de emplazamientos que contienen además por lo menos una segunda célula, los medios de selección reciben un nuevo elemento de datos que comprende la identidad de dicha conexión virtual y, como clave de selección, una hora teórica de emisión de dicha segunda célula igual a la hora teórica de emisión de dicha primera célula aumentada en el intervalo de espaciado asignado a cada conexión.

16. Espaciador según la reivindicación 14 ó 15, en el cual los índices de prioridad (u) son asignados a las conexiones virtuales, en el cual los medios de selección comprenden varios dispositivos de selección (44^{(u)}) según cualquiera de las reivindicaciones 1 a 13 tratando cada uno unos elementos de datos que comprenden unas identidades de conexiones virtuales del mismo índice de prioridad y seleccionando cada uno, entre los elementos de datos que trata, un elemento que tiene una clave de selección mínima (K^{(u)}(1)), y en el cual los medios de control de espaciado están dispuestos para mandar la emisión de una célula contenida en la cabeza de lista relativa a la conexión identificada o bien en aquél de los elementos de datos seleccionado que presenta la menor clave de selección o bien, si varios dispositivos de selección seleccionan cada uno un elemento de datos cuya clave de selección es la más pequeña, en aquél de los elementos de datos seleccionados por estos dispositivos de selección para el cual el índice de prioridad es máximo.

17. Espaciador según la reivindicación 16, en el cual los diferentes dispositivos de selección comprenden cada uno unos medios de memorización respectivos(20_{q}^{(1)}, 20_{q}^{(2)}) y comparten sus medios de control (21_{q}, 26_{q}).