способ обработки данных, узел-маршрутизатор и носитель информации

Формула изобретения

1. Способ обработки данных, включающий:

прием блока данных управления потоком от узла-источника по быстродействующему виртуальному каналу сети с коммутацией пакетов; и

направление блока данных управления потоком, передаваемого по быстродействующему виртуальному каналу, непосредственно в выходную линию для передачи в узел-получатель на основе результатов сравнения показания счетчика блокировки и порогового значения блокировки, причем: показание счетчика блокировки должно обновляться каждый раз, когда в буфере сохраняется нормальный блок данных управления потоком, предназначенный для того же порта вывода, что и блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу; блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу, должен направляться, минуя один или несколько промежуточных узлов-маршрутизаторов, без буферизации или прохождения конвейера маршрутизации в каждом из указанных промежуточных узлов-маршрутизаторов, по одному или нескольким заранее определенным маршрутам между парами узлов; и блоку данных управления потоком, передаваемому по быстродействующему виртуальному каналу, должен отдаваться приоритет по сравнению другими блоками данных управления потока, не передаваемыми по быстродействующему виртуальному каналу, в сети с коммутацией пакетов на основе только определения, что блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу, действительно, передается по быстродействующему виртуальному каналу, где нормальный блок данных управления потоком является блоком данных управления потоком, который должен быть сохранен во входном буфере перед его обработкой, и источником блока данных управления потоком должен быть узел-маршрутизатор или соседний узел узла-маршрутизатора, для которого узел-маршрутизатор является конечным пунктом быстродействующего виртуального канала, а не узлом-получателем.

2. Способ по п.1, включающий дополнительно: отслеживание блоков управления потоком, принимаемых из быстродействующего виртуального канала; включение режима устранения блокировки, если достигнуто пороговое значение блокировки; и передачу блока управления потоком, передаваемого по нормальному виртуальному каналу, в соседний узел.

3. Способ по п.1, в котором быстродействующий виртуальный канал имеет фиксированную длину.

4. Способ по п.1, в котором длина быстродействующего виртуального канала динамически изменяется.

5. Способ по п.1, в котором быстродействующий виртуальный канал представляет собой альтернативный быстродействующий виртуальный канал, если более короткий быстродействующий виртуальный канал недоступен.

6. Способ по п.1, в котором быстродействующий виртуальный канал имеет фиксированный выделенный буфер.

7. Способ по п.1, в котором быстродействующий виртуальный канал имеет динамически выделяемый буфер.

8. Узел-маршрутизатор, содержащий:

входную линию для приема блока данных управления потоком от узла-источника по быстродействующему виртуальному каналу сети с коммутацией пакетов;

выходную линию для передачи блока данных управления потоком, передаваемого по быстродействующему виртуальному каналу, в узел-получатель на основе результатов сравнения показания счетчика блокировки и порогового значения блокировки, причем показание счетчика блокировки должно обновляться каждый раз, когда в буфере сохраняется нормальный блок данных управления потоком, предназначенный для того же порта вывода, что и блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу; и

переключатель-распределитель для направления блока данных управления потоком, передаваемого по быстродействующему виртуальному каналу, непосредственно в выходную линию, причем: блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу, должен направляться, минуя один или несколько промежуточных узлов-маршрутизаторов, без буферизации или прохождения конвейера маршрутизации в каждом из указанных промежуточных узлов-маршрутизаторов, по одному или нескольким заранее определенным маршрутам между парами узлов; и блоку данных управления потоком, передаваемому по быстродействующему виртуальному каналу, должен отдаваться приоритет по сравнению другими блоками данных управления потока, не передаваемыми по быстродействующему виртуальному каналу, в сети с коммутацией пакетов на основе только определения, что блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу, действительно, передается по быстродействующему виртуальному каналу, где нормальный блок данных управления потоком является блоком данных управления потоком, который должен быть сохранен во входном буфере перед его обработкой, и источником блока данных управления потоком должен быть узел-маршрутизатор или соседний узел узла-маршрутизатора, для которого узел-маршрутизатор является конечным пунктом быстродействующего виртуального канала, а не узлом-получателем.

9. Узел-маршрутизатор по 8, который дополнительно содержит: счетчик блокировки для определения достижения порогового значения блокировки, так что блок управления потоком, передаваемый по нормальному виртуальному каналу, может достичь соседнего узла.

10. Узел-маршрутизатор по п.8, в котором быстродействующий виртуальный канал имеет фиксированную длину.

11. Узел-маршрутизатор по п.8, в котором длина быстродействующего виртуального канала динамически изменяется.

12. Узел-маршрутизатор по п.8, в котором быстродействующий виртуальный канал представляет собой альтернативный быстродействующий виртуальный канал, если более короткий быстродействующий виртуальный канал недоступен.

13. Узел-маршрутизатор по п.8, в котором быстродействующий виртуальный канал имеет фиксированный выделенный буфер.

14. Узел-маршрутизатор по п.8, в котором быстродействующий виртуальный канал имеет динамически выделяемый буфер.

15. Узел-маршрутизатор по п.8, в котором сеть с коммутацией пакетов представляет собой однокристальный мультипроцессор.

16. Носитель информации с набором команд, который может быть выполнен процессором для осуществления способа обработки данных, включающего:

прием блока данных управления потоком от узла-источника по быстродействующему виртуальному каналу сети с коммутацией пакетов; и

направление блока данных управления потоком, передаваемого по быстродействующему виртуальному каналу, непосредственно в выходную линию для передачи в узел-получатель на основе результатов сравнения показания счетчика блокировки и порогового значения блокировки, причем: показание счетчика блокировки должно обновляться каждый раз, когда в буфере сохраняется нормальный блок данных управления потоком, предназначенный для того же порта вывода, что и блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу; блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу, должен направляться, минуя один или несколько промежуточных узлов-маршрутизаторов, без буферизации или прохождения конвейера маршрутизации в каждом из указанных промежуточных узлов-маршрутизаторов, по одному или нескольким заранее определенным маршрутам между парами узлов; и блоку данных управления потоком, передаваемому по быстродействующему виртуальному каналу, должен отдаваться приоритет по сравнению другими блоками данных управления потока, не передаваемыми по быстродействующему виртуальному каналу, в сети с коммутацией пакетов на основе только определения, что блок данных управления потоком, передаваемый по быстродействующему виртуальному каналу, действительно, передается по быстродействующему виртуальному каналу, где нормальный блок данных управления потоком является блоком данных управления потоком, который должен быть сохранен во входном буфере перед его обработкой, и источником блока данных управления потоком должен быть узел-маршрутизатор или соседний узел узла-маршрутизатора, для которого узел-маршрутизатор является конечным пунктом быстродействующего виртуального канала, а не узлом-получателем.

17. Носитель по п.16, содержащий дополнительно: отслеживание блоков управления потоком, принимаемых из быстродействующего виртуального канала; включение режима устранения блокировки, если достигнуто пороговое значение блокировки; и передачу блока управления потоком, передаваемого по нормальному виртуальному каналу, в соседний узел.

18. Носитель по п.16, в котором длина быстродействующего виртуального канала динамически изменяется.

19. Носитель по п.16, в котором быстродействующий виртуальный канал представляет собой альтернативный быстродействующий виртуальный канал, если оптимальный быстродействующий виртуальный канал недоступен.

20. Носитель по п.16, в котором быстродействующий виртуальный канал имеет динамически выделяемый буфер.

Описание изобретения к патенту

1. Область техники

[0001] Настоящее изобретение относится в целом к области обмена информацией между компонентами однокристального мультипроцессора. Более конкретно, изобретение относится к формированию быстродействующих виртуальных каналов обмена информацией между компонентами однокристального мультипроцессора.

2. Введение

[0002] Однокристальный мультипроцессор или специализированные системы на одном кристалле могут иметь несколько компонентов, которые должны обмениваться информацией друг с другом. Такими компонентами могут быть процессор, кэш-память (сверхоперативное ЗУ), регистр данных и другие компоненты. Компоненты кристалла могут обмениваться данными, используя систему шины или систему фиксированных соединений. Любая такая система может требовать осуществления очень большого количества соединений, которые могут занимать так необходимое место на кристалле, и, кроме того, между передаваемыми сигналами могут возникать помехи.

[0003] Компоненты могут обмениваться данными с использованием системы коммутации пакетов, которая позволяет более эффективно использовать место на кристалле. Система коммутации пакетов может работать, передавая пакеты данных между компонентами, в результате чего уменьшается количество фиксированных соединений между двумя компонентами.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0004] Изобретение описывается ниже подробно со ссылками на прилагаемые чертежи, которые используются лишь для иллюстрации типичных вариантов осуществления изобретения и поэтому не должны рассматриваться как ограничивающие его объем, и на которых показано:

[0005] фигура 1 - блок-схема одного из вариантов передачи пакетов данных между компонентами однокристального мультипроцессора;

[0006] фигура 2 - схема одного из вариантов сети компонентов на кристалле в форме двухмерной сотовой сети;

[0007] фигура 3 - блок-схема одного из вариантов микроархитектуры узла-маршрутизатора, в котором реализуется быстродействующий виртуальный канал;

[0008] фигура 4 - схема одного из вариантов сети компонентов на кристалле, в котором используются динамические быстродействующие виртуальные каналы, в форме двухмерной сотовой сети;

[0009] фигура 5 - блок-схема одного из вариантов сети компонентов на кристалле, в котором используются динамические быстродействующие виртуальные каналы с гибкой маршрутизацией;

[0010] фигура 6 - блок-схема алгоритма, осуществляющего один из вариантов способа обработки данных пакета, полученного из виртуального канала, узлом-маршрутизатором;

[0011] фигура 7 - иллюстрация в форме сотовой сети одного из вариантов возникновения блокировки в сети с быстродействующими виртуальными каналами;

[0012] фигура 8 - временная диаграмма для одного из вариантов системы управления буферизацией для нормального виртуального канала с использованием разрешений на передачу очередного пакета данных;

[0013] фигура 9 - временная диаграмма для одного из вариантов системы управления буферизацией для быстродействующего виртуального канала с использованием разрешений на передачу очередного пакета данных;

[0014] фигура 10 - иллюстрация в форме блок-схемы одного из вариантов счетчика буфера для системы управления фиксированными буферами;

[0015] фигура 11 - иллюстрация в форме блок-схемы одного из вариантов счетчика буфера для системы управления динамически выделяемыми буферами;

[0016] фигура 12 - иллюстрация в форме блок-схемы одного из вариантов комбинации путей, которые могут использоваться для обмена данными с заданным узлом;

[0017] фигура 13 - иллюстрация в форме блок-схемы одного из вариантов статического выделения виртуальных каналов;

[0018] фигура 14 - иллюстрация в форме блок-схемы одного из вариантов компьютерной системы, которая может работать в качестве узла-маршрутизатора.

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

[0019] Другие особенности и достоинства изобретения будут рассмотрены в нижеприведенном описании и отчасти будут очевидны из настоящего описания или же могут стать понятными из вариантов осуществления изобретения. Особенности и достоинства изобретения могут быть реализованы и получены с использованием устройств и конфигураций, указанных в прилагаемой формуле. Эти и другие особенности настоящего изобретении станут более очевидными из нижеприведенного описания и прилагаемой формулы изобретения или же могут стать понятными из вариантов осуществления изобретения.

[0020] Ниже подробно рассматриваются различные варианты осуществления изобретения. В описании рассматриваются некоторые конкретные варианты осуществления изобретения и следует понимать, что они приведены лишь в целях иллюстрации изобретения. Специалисту в данной области техники будет ясно, что могут быть использованы и другие компоненты и конфигурации без выхода за пределы объема и сущности изобретения.

[0021] Настоящее изобретение содержит несколько вариантов его осуществления, такие как способ, устройство и набор компьютерных команд, а также другие варианты, которые связаны с основными идеями изобретения. В изобретении предлагается способ, узел маршрутизации и набор команд для использования быстродействующих виртуальных каналов в сети компонентов на одном кристалле. Во входную линию по быстродействующему виртуальному каналу сети с коммутацией пакетов может приниматься блок управления потоком (flow control unit - флит) по быстродействующему каналу от узла-источника. Блок управления потоком по быстродействующему каналу может передаваться из выходной линии в узел-получатель. Блок управления потоком по быстродействующему каналу может быть направлен непосредственно в выходную линию переключателем-распределителем.

[0022] Однокристальный мультипроцессор или специализированная система на одном кристалле может иметь несколько компонентов, которые должны обмениваться информацией друг с другом. Для обмена данными между такими компонентами может использоваться технология коммутации пакетов, реализация которой не требует много места на кристалле. На фигуре 1 приведена блок-схема одного из вариантов системы 100 передачи данных между компонентами однокристального мультипроцессора. Некоторый компонент, выступающий в роли узла-источника 102, может организовать некоторый набор данных в пакет. Пакет данных может быть разделен на несколько блоков управления потоком (БУП). Узел-источник 102 может передавать каждый БУП в ближайший доступный компонент. Принимающий компонент, выступающий в роли узла-маршрутизатора 104, может передавать данные в следующий ближайший доступный компонент, пока не будет достигнут компонент, выступающий в роли узла-получателя 106. Путь, по которому БУП проходит от узла-источника 102 к узлу-получателю 106, может быть организован как виртуальный канал. В нормальном виртуальном канале (НВ-канал) 108 узел-источник 102 может передавать БУП в узел-маршрутизатор 104, который может осуществлять промежуточное хранение БУП в буфере, организовывать этот БУП вместе с другими БУП, поступившими по конвейеру, и затем передавать их в выходную линию для передачи в следующий узел-маршрутизатор 104 или в узел-получатель 106.

[0023] Для уменьшения различий в быстродействии и энергетических затратах между сетью с коммутацией пакетов, формируемой на кристалле, и идеальной сетью межкомпонентных соединений может использоваться быстродействующий виртуальный канал (БВ-канал), позволяющий достичь времени передачи и энергетических затрат выделенного канала связи. БВ-канал 110 может обеспечивать передачу, при которой БУП могут проходить по заранее определенным маршрутам между парами узлов, минуя промежуточные узлы-маршрутизаторы 104. БУП, проходящий по БВ-каналу 110, может иметь приоритет перед другими БУП, в результате чего обеспечивается возможность непосредственного использования ими выходной линии без их буферизации и без прохождения ими конвейера маршрутизации в каждом узле-маршрутизаторе 104. БВ-канал 110 может облегчать создание потоков внутри сети, как это происходит, например, при коммутации каналов без какого-либо этапа настройки, в результате чего существенно сокращаются времена ожидания при передаче пакетов. Более того, поскольку эти БУП не проходят через промежуточные узлы-маршрутизаторы 104, БВ-канал 110 может снизить потери, связанные с буферизацией, переключением маршрутизаторов и конфликтами, возникающими при передачах между маршрутизаторами, в результате чего повышается эффективность использования энергии и места на кристалле.

[0024] На фигуре 2 приведена схема одного из вариантов сети компонентов на кристалле в форме двухмерной сотовой сети 200. Хотя здесь указывается сеть с коммутацией пакетов для однокристального мультипроцессора, БВ-канал 110 может использоваться в любой сети с коммутацией пакетов. Необходимо иметь в виду, что размеры и двухмерный характер сотовой сети указываются лишь в целях иллюстрации и никоим образом не являются ограничениями для целей настоящего изобретения. Каждый узел 202 может выступать в роли узла-источника 102, узла-маршрутизатора 104 и узла-получателя 106. Каждый узел 202 в сети 200 может быть соединен с соседним узлом 202 с использованием НВ-канала 108. Кроме того, узел 202 может соединяться с другими (несоседними) узлами с использованием БВ-канала 110 по заранее определенному маршруту без ожиданий или буферизации в каком-либо из узлов-маршрутизаторов 104, то есть БУП не проходит через промежуточные узлы или узлы-маршрутизаторы 104. Например, БУП, передаваемый от узла B к узлу G, может проходить по НВ-каналу 108 от узла B до узла D и затем использовать БВ-канал 110 для прохождения от узла D к узлу G. БВ-канал 110 может исключать времена ожидания при прохождении данных через узлы-маршрутизаторы 104, узлы E и F в данном случае, и позволяет экономить энергию, исключая все операции по буферизации на узлах-маршрутизаторах 104. В сети с фиксированными БВ-каналами определенные узлы-источники 102 могут быть соединены с узлами-получателями 106 с использованием БВ-каналов 110. В приведенном примере используется фиксированный БВ-канал 110 длиной в четыре узла, однако при необходимости может использоваться фиксированный БВ-канал ПО большей или меньшей длины.

[0025] Маршрутизатор может осуществлять быстродействующие соединения в рамках управления потоками данных по виртуальным каналам. Маршрутизатор может назначать виртуальные каналы, которые могут заниматься только пакетами данных, передаваемыми по скоростным маршрутам (прокладываемым по БВ-каналам). На фигуре 3 приведена блок-схема одного из вариантов микроархитектуры 300 узла-маршрутизатора, на котором реализуется БВ-канал 110. Узел-маршрутизатор 104 может принимать БУП по виртуальному каналу во входную линию 302 и направлять принятый БУП в модуль 304 управления потоками данных. Виртуальные каналы, используемые для управления потоками данных, могут быть организованы в группы НВ-каналов 108 и БВ-каналов 110. Модуль 304 управления потоками данных может использовать виртуальные каналы для определения приоритета БУП при выборе БУП, который должен быть направлен в выходную линию 306, задаваемую координатным коммутатором 308.

[0026] Логический модуль 310 определения маршрута на каждом узле-маршрутизаторе 104 может рассчитывать маршрут или путь пакета данных, передаваемого от узла-источника 102 в узел-получатель 106. Логический модуль 310 определения маршрута может обеспечивать определение возможности назначения пакета данных для передачи по БВ-каналу 110. Кроме того, логический модуль 310 определения маршрута может выполнять предварительную маршрутизацию для всех пакетов данных, так что когда пакет данных достигает узла или конечного пункта БВ-канала 110, то отпадает необходимость в определении маршрута для критической части конвейера маршрутизатора. Вычисление маршрута не должно никоим образом влиять на используемый базовый алгоритм маршрутизации. В узле-маршрутизаторе используется распределитель 312 БВ-каналов, который может назначать БВ-канал 110 пакету данных, для которого предполагается использоваться скоростной маршрут между двумя узлами, в то время как распределитель 314 НВК может назначать НВ-канал 108 другому пакету данных, который предполагается передавать в соседний узел.

[0027] Модуль 304 управления потоками данных может принимать БУП из БВ-канала 110 через входной буфер БВ-канала (БВК БУФ) 316 или из НВ-канала 108 через входной буфер НВ-канала (НВК БУФ) 318. Триггер-фиксатор 320 БВК может организовывать БУП, когда он проходит через любой узел-маршрутизатор 104 по БВ-каналу 110. БУП, проходящий через триггер-фиксатор 320 БВ-канала, может получать преимущественную возможность передачи через выходной порт 306 по сравнению с другими пакетами. Триггер-фиксатор 320 БВ-канала может прерывать текущую передачу пакетов данных между двумя узлами, например, потока данных по БВ-каналу, имеющего меньший приоритет.

[0028] Коммутатор-распределитель 322 может отдавать предпочтение потоку данных по БВ-каналу 110 перед потоком данных по НВ-каналу 108. Коммутатор-распределитель 322 может прерывать поток БУП по БВ-каналу 110 всего лишь с несколькими переходами на узле-источнике 102, так что поток БУП по БВ-каналу 110 может использовать узел-маршрутизатор с большим количеством переходов. Коммутатор-распределитель 322 может прерывать поток БУП по БВ-каналу 110 на ближайшем узле-источнике 102, так что поток БУП по БВ-каналу 110 от более удаленного узла-источника 102 может использовать этот узел-маршрутизатор 104.

[0029] Сеть 200 может быть фиксированным образом разделена на БВ-каналы 110 и НВ-каналы 108 или же в ней могут использоваться динамически формируемые виртуальные каналы. На фигуре 4 приведена схема одного из вариантов сети 400 компонентов с коммутацией пакетов, в которой используются динамические БВ-каналы, в форме двухмерной сотовой сети 400. В сети с коммутацией пакетов, в которой осуществляется динамическое формирование БВ-каналов, любая группа переходов между узлами 202 может быть указана как динамический БВ-канал 402. Длина маршрута 402 по БВ-каналам может быть рассчитана, как это необходимо для маршрута определенных данных, в пределах максимальной длины БВ-каналов, определяемой ограничениями компонентов сети. Например, в сети 200 с фиксированными БВ-каналами узел-источник 102 может перемещаться от узла B к узлу C и от узла C к узлу D посредством одного перехода по маршруту НВ-канала 108 и от узла D к узлу G по маршруту фиксированного БВ-канала 110. В динамической сети, в которой допускается максимальная длина БВ-каналов 402 в три перехода, узел-источник 102 может передать БУП непосредственно из узла B в узел E, а затем использовать подмножество маршрута по БВ-каналу 402 длиной в два перехода для перемещения в узел G, и т.д.

[0030] На фигуре 5 приведена блок-схема одного из вариантов сети 500 компонентов на кристалле, в которой используются динамические БВ-каналы с гибкой маршрутизацией. В некоторые моменты невозможно сформировать оптимальный БВ-канал 502, такой как самый длинный маршрут, из-за ограничений компонентов. В этом случае узел-источник 102 может передавать БУП по альтернативному БВ-каналу 504, такому как следующий более короткий БВ-канал 504, с использованием доступных ресурсов. Например, наиболее эффективным маршрутом для передачи БУП из узла-источника A в узел-получатель G может быть непосредственная передача БУП из узла-источника A в узел D по первому оптимальному БВ-каналу 502, и затем от узла-маршрутизатора D в узел-получатель G по второму оптимальному БВ-каналу 502. Однако наиболее оптимальный маршрут передачи данных может не обеспечиваться имеющимися ресурсами. Узел-источник A может передать БУП в узел-получатель по альтернативному маршруту 504. Узел-источник A может передать БУП по альтернативному БВ-каналу 504 в узел-маршрутизатор C, затем из узла-маршрутизатора C данные передаются в узел-маршрутизатор E, а из узла-маршрутизатора E в узел-получатель G. Распределитель 212 БВ-канала может определить наилучший маршрут с учетом информации маршрутизации, содержащейся в пакете данных.

[0031] На фигуре 6 приведена блок-схема алгоритма, осуществляющего один из вариантов способа 600 обработки БУП, полученного из виртуального канала, узлом-маршрутизатором. Узел-маршрутизатор 104 может принимать БУП по виртуальному каналу (блок 602). Если БУП является нормальным БУП (НБ, блок 604), то узел-маршрутизатор 104 может записать его во входной буфер (блок 606) для последующей обработки (блок 608). Нормальный БУП может быть БУП, для которого узел-маршрутизатор 104 является узлом-источником 102, может быть БУП, который получен узлом-маршрутизатором 104 от соседнего узла по НВ-каналу 108, или же может быть БУП, для которого узел-маршрутизатор является конечным пунктом БВ-канала 110, но не узлом-получателем 106. Входной порт может быть входным буфером 318 НВ-канала, если БУП получен по НВ-каналу 108, или входным буфером 316, если БУП получен по БВ-каналу 110. Узел-маршрутизатор 104 может передать обработанный нормальный БУП в выходную линию 306 (блок 610). Если БУП является скоростным БУП (БУП, передаваемый по БВ-каналу - СБ), то узел-маршрутизатор 104 может направить скоростной БУП в выходную линию 306 (блок 612). Скоростной БУП может быть БУП, принимаемым узлом-маршрутизатором 104 в середине БВ-канала 110.

[0032] В любой сети, в которой заранее устанавливается определенная пропускная способность для передачи сообщений, может возникать блокировка, когда сообщения, передаваемые по такой сети, блокируют другие сообщения. На фигуре 7 приведена иллюстрация для сотовой сети одного из вариантов ситуации блокировки 700 в сети с БВ-каналами. Более высокий приоритет, назначаемый скоростным БУП 702, может приводить к возникновению блокировки. Например, если в узле-маршрутизаторе D вдоль БВ-канала 702 постоянно имеются скоростные БУП для передачи по БВ-каналам, то для нормальных БУП никогда не появится возможность использования физического канала. Пакет данных для передачи по БВ-каналу из вышележащего (по направлению потока информации) узла-источника может также постоянно блокировать передачу по другому БВ-каналу пакета данных из нижележащего узла-источника.

[0033] Для предотвращения возникновения такой ситуации каждый узел-маршрутизатор 104 может поддерживать работу счетчика последовательных циклов, для которых узел-маршрутизатор 104 обслуживал определенный БВ-канал 110. После обслуживания скоростных БУП в заданном количестве последовательных циклов узел-маршрутизатор 104 может передать сообщение о блокировке, такое как, например, сообщение Начать процедуру снятия блокировки или индикатор Блокировка , в направлении узла-источника A по каналам разрешения на передачу очередного пакета данных. После получения этого индикатора узел-источник A может прекратить передачу скоростных БУП по соответствующей линии, в результате чего может быть обслужен заблокированный БУП. Через заданное количество циклов узел-маршрутизатор D может передать в узел-источник A сообщение Закончить процедуру снятия блокировки или индикатор Блокировка снята , которые указывают на то, что можно возобновить передачу скоростных БУП.

[0034] Как показано на фигуре 6, если нормальный БУП, назначенный для передачи в тот же порт 306 вывода, что и скоростной БУП, сохраняется в буфере (блок 614), то узел-маршрутизатор 104 может увеличивать на единицу показание счетчика блокировки (блок 616). Узел-маршрутизатор 104 может проверять (блок 618), превысила ли величина SCT заданное пороговое значение (STHR). Если величина SCT достигла значения STHR, то узел-маршрутизатор 104 может передать сообщение Начать процедуру снятия блокировки (BSRM) во все вышележащие узлы-источники 102 скоростных БУП (блок 620). После окончания интервала времени, в течение которого все соответствующие вышележащие узлы получат сообщение Когда узел-маршрутизатор 104 находится в режиме устранения блокировки, узлы-источники 102, передающие пакеты данных по БВ-каналу, могут приостановить передачу таких пакетов, осуществить поиск альтернативного маршрута или предпринять другие соответствующие действия. Узел-маршрутизатор 104 может сбросить счетчик (SRP) периода устранения блокировки в нуль (блок 622).

[0035] Если узел-маршрутизатор 104 не находится в режиме устранения блокировки (блок 624), то для нормального БУП он может сбросить SCT в нуль (блок 626). Если узел-маршрутизатор 104 находится в режиме устранения блокировки (блок 624), то он может увеличить значение SRP на единицу, когда нормальный БУП успешно направлен в порт 306 вывода (блок 628). По окончании периода устранения блокировки (блок 630) узел-маршрутизатор 104 может передать сообщение Закончить устранение блокировки (ESRM) во все вышележащие узлы-источники 102, передающие пакеты данных по БВ-каналу, указывая на то, что узел-маршрутизатор 104 снова принимает скоростные БУП (блок 632).

[0036] Сеть компонентов на кристалле может использовать технику управления потоками с буферизацией для управления буферами и передачи сообщений об их доступности между соседними узлами-маршрутизаторами 104. Нижележащий узел может передавать сообщение о числе свободных буферов в вышележащий узел по каналу обратной связи. Для управления буферами с использованием каналов разрешения на передачу очередного пакета данных может использоваться вышележащий маршрутизатор для ведения счетчика количества свободных буферов, имеющихся ниже по потоку. Показания счетчика могут уменьшаться на единицу каждый раз при передаче БУП, в результате чего будет заниматься нижележащий буфер. Когда БУП выходит из нижележащего узла и освобождает соответствующий буфер, вверх по потоку может быть передано разрешение на передачу очередного пакета данных, и соответствующее показание счетчика свободных буферов может быть увеличено на единицу.

[0037] Сеть компонентов может использовать простую логику управления буферами для фиксированного выделения буферов для каждого виртуального канала, соответствующих времени задержки получения разрешения на передачу очередного пакета данных для этого виртуального канала. На фигуре 8 приведена временная диаграмма для одного из вариантов системы 800 управления буферами НВ-каналов 108, действующей с использованием разрешений на передачу очередных пакетов данных. В момент t₁ времени узел B передает БУП в следующий узел (стрелка 802), при этом в интервале между t₁ и t₂ узел B может передать в узел A разрешение на передачу очередного пакета данных (стрелка 804). Узел A может обрабатывать полученное разрешение между t₂ и t₃ (стрелка 806). Узел A может передать разрешение на передачу очередного пакета данных (стрелка 804) при передаче БУП в узел B между t₃ и t₄ (стрелка 802). Узел B может обрабатывать БУП в конвейере, который не является высокоскоростным конвейером, в интервале от t₄ до t₅ (стрелка 808). Таким образом, полное время задержки (T_CRN) разрешения может составлять интервал времени от t₁ до t₅.

[0038] При использовании БВ-канала 110 передача информации о наличии буфера может быть выполнена на нескольких переходах для обеспечения свободного буфера на нижележащем узле-получателе 106 для передачи по БВ-каналу. Передача информации о наличии буфера через несколько переходов может приводить к увеличению задержки, в результате чего снижается пропускная способность. На фигуре 9 приведена временная диаграмма для одного из вариантов системы 900 управления буферами БВ-канала 110, действующей с использованием разрешений на передачу очередных пакетов данных. В момент t₁ времени узел D передает БУП в следующий узел (стрелка 902), при этом в интервале между t₁ и t₂ узел D передает в узел A разрешение на передачу очередного пакета данных (стрелка 904). Узел A может обрабатывать полученное разрешение между t ₂ и t₃ (стрелка 906). Узел A может передать разрешение на передачу очередного пакета данных (стрелка 904) при передаче БУП в узел B между t₃ и t₄ (стрелка 902). Узел B может передать БУП в выходную линию, являющуюся частью высокоскоростного конвейера, в интервале от t₄ до t₅ (стрелка 908). Узел B может передать БУП в узел C в интервале между t₅ и t₆ (стрелка 902). Узел C может передать БУП в выходную линию, являющуюся частью высокоскоростного конвейера, в интервале от t₆ до t₇ (стрелка 908). Узел C может передать БУП в узел D в интервале между t₇ и t₈ (стрелка 902). Узел C может обрабатывать БУП в конвейере, который не является высокоскоростным конвейером, в интервале от t₈ до t₉ (стрелка 910). Таким образом, полное время задержки (T_CRE) разрешения может составлять интервал времени от t₁ до t₉.

[0039] В системе управления буферами может использоваться схема фиксированных буферов. На фигуре 10 приведена иллюстрация в форме блок-схемы одного из вариантов счетчика буфера для системы 1000 управления фиксированными буферами. Каждому виртуальному каналу может быть назначено фиксированное количество буферов, выделенных для БУП, проходящих по этому виртуальному каналу. Группа буферов 1002 может быть выделена для каждого НВ-канала 108, и группа буферов 1004 может быть выделена для каждого БВ-канала 110. Размер каждой группы буферов 1004 может выбираться с учетом времени T_CRE .

[0040] Система управления с фиксированным размером групп буферов может быть неэффективной в случае возникновения конфликтов. Например, если большая часть трафика в сети представляет собой обмен между соседними узлами, то БВ-каналы могут вообще не использоваться, и буферная память, выделенная БВ-каналам 110, будет простаивать. Вместо фиксированного разделения буферов по типам каналов, таким как НВ-каналы 108 и БВ-каналы 110, буферы могут выделяться виртуальному каналу по запросу. Для указания вышележащему узлу об используемом БВ-канале может использоваться схема наивысшего уровня, которая задает БВ-каналам 402 с малым числом переходов или НВ-каналам 108 более высокий приоритет по сравнению с маршрутами с бóльшим числом переходов, когда буферы становятся доступными. Например, если БВ-канал 402 с двумя переходами требует по меньшей мере восьми доступных буферов, то нижележащий маршрутизатор может передать в вышележащий маршрутизатор сообщение о том, что БВ-канал 402 доступен, когда показание счетчика в нижележащем маршрутизаторе равно восьми. Допускается свободная передача буферов между виртуальными каналами, так чтобы один виртуальный канал мог иметь только один БУП.

[0041] На фигуре 11 приведена иллюстрация в форме блок-схемы одного из вариантов счетчика буфера для системы управления с динамическим выделением буферов. Счетчик 1102 буфера может указывать количество доступных, или свободных, буферов. Если счетчик 1102 буфера указывает, что число доступных буферов равно пороговой величине 1104 для НВ-канала, которая определяет количество буферов, необходимых для работы НВ-канала 108, то узел может использовать этот канал. Если счетчик 1102 буфера указывает, что число доступных буферов равно пороговой величине 1106 для БВ-канала, которая определяет количество буферов, необходимых для работы БВ-канала 402, то узел может использовать этот канал. Пороговая величина 1106 для БВ-канала может быть связана с длиной БВ-канала 402.

[0042] Для обеспечения гибкой буферизации нижележащий маршрутизатор должен иметь возможность передавать соответствующие сигналы в вышележащие маршрутизаторы. На фигуре 12 приведена иллюстрация в форме блок-схемы одного из вариантов комбинации 1200 маршрутов, которые могут использоваться для обмена информацией с заданным узлом. На фигуре 12 показана сеть из восьми узлов, однако могут использоваться сети и других размеров.

[0043] Может использоваться фиксированное выделение виртуальных каналов. На фигуре 13 приведена иллюстрация в форме таблицы одного из вариантов фиксированного выделения 1300 виртуальных каналов. Общее количество виртуальных каналов 1302 может быть разделено между НВ-каналами 108 и БВ-каналами 402, имеющими разную длину. Такое разделение осуществляют на стадии проектирования. Для сети компонентов, в которой максимальная длина БВ каналов может быть равна I_MAX, может быть обеспечен набор виртуальных каналов общим числом (k×I_MAX). В системе компонентов количество выделенных НВ-каналов 108 может быть равно k₁ , количество выделенных БВ-каналов 402, имеющих длину 2, может быть равно k₂, количество выделенных БВ-каналов 402, имеющих длину 3, может быть равно k₃, и т.д.

[0044] На фигуре 14 приведена возможная схема вычислительной системы 1400, используемой в качестве узла-маршрутизатора 104 в сети с коммутацией пакетов. Узел-маршрутизатор 104 может содержать контроллер/процессор 1410, запоминающее устройство 1420 и сетевой интерфейс 1430, причем указанные устройства соединены между собой по шине 1440. В узле-маршрутизаторе 104 может быть использована любая операционная система, такая как, например, Microsoft Windows®, UNIX или LINUX. Программы клиента и сервера могут быть написаны на любом языке программирования, таком как, например, C, C++, Java или Visual Basic. Программа сервера может работать в любой среде приложений, такой как, например, сервер Java® или платформа .NET®.

[0045] В качестве контроллера/процессора 1410 может быть использован любой программируемый процессор, известный специалистам. Однако способ поддержки принятия решений может быть также реализован на универсальном или специализированном компьютере, на программируемом микропроцессоре или микроконтроллере, на периферийных элементах интегральных схем, на специализированных или других интегральных схемах, на аппаратных/электронных логических схемах, таких как схемы на дискретных элементах, на программируемых логических устройствах, таких как программируемые логические матрицы, программируемые пользователем вентильные матрицы и т.п. Вообще говоря, любое устройство или устройства, способные осуществлять вышеописанный способ маршрутизации с использованием БВ-каналов, могут использоваться для реализации функций системы поддержки принятия решений в соответствии с настоящим изобретением.

[0046] В качестве запоминающего устройства 1420 может использоваться энергонезависимое устройство хранения данных, включая одно или несколько электрических, магнитных или оптических устройств, таких как оперативное ЗУ, сверхоперативное ЗУ (кэш-память), жесткий диск или другое запоминающее

устройство. Запоминающее устройство может быть снабжено кэш-памятью для ускорения доступа к определенным данным. Запоминающее устройство 1420 может быть также подсоединено к ПЗУ на компакт-дисках, к ПЗУ на DVD, к ЗУ на DVD с возможностью записи, к ЗУ на магнитной ленте или к другому съемному запоминающему устройству, которые обеспечивают непосредственную загрузку данных в систему.

[0047] Сетевой интерфейс 1430 может быть соединен с устройством связи, с модемом, с сетевой интерфейсной картой, с приемопередатчиком или другим устройством, способным передавать и принимать сигналы из сети. Сетевой интерфейс 1430 может использоваться для подсоединения узла-маршрутизатора 104 к сети. Компоненты узла-маршрутизатора 104 могут быть соединены между собой по электрической шине 1440 или связаны с помощью средств беспроводной связи.

[0048] Контроллер/процессор 1410 может получать доступ к находящимся в запоминающем устройстве 1420 программам клиента и к базам данных, которые могут включать, например, базы данных приложений, текстовые редакторы, а также компоненты, которые обеспечивают реализацию функций поддержки принятия решений в соответствии с настоящим изобретением. В узле-маршрутизаторе 104 может быть использована любая операционная система, такая как, например, Microsoft Windows®, UNIX или LINUX. Программы клиента и сервера могут быть написаны на любом языке программирования, таком как, например, C, C++, Java или Visual Basic. Хотя это и не является обязательным требованием, изобретение описывается, по меньшей мере частично, в общем контексте исполняемых компьютером наборов команд, таких как программные модули, исполняемые электронным устройством, таким как компьютер общего назначения. В общем случае программные модули включают стандартные программы, объекты, компоненты, структуры данных и т.п., которые выполняют определенные задания или обеспечивают использование определенных типов данных. Специалистам в данной области техники будет ясно, что в сетевых вычислительных средах с различными типами компьютерных систем могут быть осуществлены другие варианты осуществления изобретения, включая персональные компьютеры, карманные устройства, мультипроцессорные системы, бытовые электронные устройства на микропроцессорах или программируемые, сетевые ПК, мини-компьютеры, большие ЭВМ и т.п.

[0049] Хотя это и не является обязательным требованием, изобретение описывается, по меньшей мере частично, в общем контексте исполняемых компьютером наборов команд, таких как программные модули, исполняемые электронным устройством, таким как компьютер общего назначения. В общем случае программные модули включают стандартные программы, объекты, компоненты, структуры данных и т.п., которые выполняют определенные задания или обеспечивают использование определенных типов данных. Специалистам в данной области техники будет ясно, что в сетевых вычислительных средах с различными типами компьютерных систем могут быть осуществлены другие варианты осуществления изобретения, включая персональные компьютеры, карманные устройства, мультипроцессорные системы, бытовые электронные устройства на микропроцессорах или программируемые, сетевые ПК, мини-компьютеры, большие ЭВМ и т.п.

[0050] Некоторые варианты осуществления изобретения также могут использоваться в распределенных вычислительных средах, в которых задания выполняются местным и удаленным устройствами обработки данных, которые соединяются посредством телекоммуникационной сети (с использованием проводных или беспроводных каналов связи или их сочетаний).

[0051] В рамках объема настоящего изобретения его варианты могут также включать машиночитаемый носитель, на котором могут записываться и храниться исполняемые инструкции или структуры данных. В качестве такого машиночитаемого носителя может использоваться любой носитель, к которому может иметь доступ специализированный или универсальный компьютер. В качестве такого машиночитаемого носителя может использоваться, например, ОЗУ, ПЗУ, ЭСППЗУ, ПЗУ на компакт-дисках, или другие запоминающие устройства на оптических или магнитных дисках, или другие магнитные запоминающие устройства, или другой носитель, который может использоваться для записи и хранения структур данных или необходимых программных кодов в форме исполняемых компьютером команд. Когда информация передается или обеспечивается по сети или с помощью других средств связи (с использованием проводных или беспроводных каналов связи или их сочетаний) с компьютером, то для компьютера такое соединение представляет по существу машиночитаемую среду. Таким образом, любое такое соединение по существу может быть названо машиночитаемой средой. Сочетания вышеуказанных средств также могут быть включены в объем понятия машиночитаемого носителя.

[0052] Исполняемые компьютером инструкции включают, например, команды и данные, которые обеспечивают выполнение универсальным или специализированным компьютером, или специализированным устройством обработки данных определенной функции или группы функций. Исполняемые компьютером инструкции также включают программные модули, которые выполняются компьютером в автономном режиме или в сетевой среде. В общем случае программные модули включают стандартные программы, объекты, компоненты, структуры данных и т.п., которые выполняют определенные задания или обеспечивают использование определенных типов данных. Исполняемые компьютером инструкции, связанные с ними структуры данных и программные модули представляют собой примеры программных средств, обеспечивающих выполнение стадий предлагаемых в изобретении способов. Определенная последовательность таких исполняемых инструкций или связанных с ними структур данных представляет собой примеры соответствующих действий для реализации функций, указанных на таких стадиях.

[0053] Конкретные детали, указанные в вышеприведенном описании вариантов изобретения, никоим образом не должны рассматриваться ограничивающими объем, который определяется формулой изобретения. Другие конфигурации вышеописанных вариантов осуществления изобретения являются частью его объема. Например, принципы изобретения могут быть применены к каждому отдельному пользователю, в результате чего каждый пользователь может в индивидуальном порядке применять такую систему. Это дает каждому пользователю возможность использовать достоинства изобретения, даже если для большого числа возможных применений не требуется полный объем функций, указанных в описании. Множество экземпляров электронных устройств может осуществлять обработку данных различными возможными способами. Совершенно необязательно, чтобы одна система использовалась всеми конечными пользователями. Соответственно, только прилагаемая формула изобретения и допустимые законодательством эквиваленты ее пунктов должны определять изобретение, а не какие-либо приведенные конкретные примеры.