[go: up one dir, main page]

KR20030009334A - 복수개의 제어선을 이용한 복수 단계 최소 로직네트워크상의 처리능력을 증가시키는 확장성 장치 및 방법 - Google Patents

복수개의 제어선을 이용한 복수 단계 최소 로직네트워크상의 처리능력을 증가시키는 확장성 장치 및 방법 Download PDF

Info

Publication number
KR20030009334A
KR20030009334A KR1020027007842A KR20027007842A KR20030009334A KR 20030009334 A KR20030009334 A KR 20030009334A KR 1020027007842 A KR1020027007842 A KR 1020027007842A KR 20027007842 A KR20027007842 A KR 20027007842A KR 20030009334 A KR20030009334 A KR 20030009334A
Authority
KR
South Korea
Prior art keywords
node
nodes
message
data
control signal
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
KR1020027007842A
Other languages
English (en)
Inventor
코크 에스. 리드
존 이. 헤씨
Original Assignee
인터랙틱 홀딩스 엘엘시
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 인터랙틱 홀딩스 엘엘시 filed Critical 인터랙틱 홀딩스 엘엘시
Publication of KR20030009334A publication Critical patent/KR20030009334A/ko
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01R—MEASURING ELECTRIC VARIABLES; MEASURING MAGNETIC VARIABLES
    • G01R31/00—Arrangements for testing electric properties; Arrangements for locating electric faults; Arrangements for electrical testing characterised by what is being tested not provided for elsewhere
    • G01R31/08—Locating faults in cables, transmission lines, or networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H04L45/04—Interdomain routing, e.g. hierarchical routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H04L45/06—Deflection routing, e.g. hot-potato routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/30—Routing of multiclass traffic
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/15—Interconnection of switching modules

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

계층적인 다수의 단계 구조 내에 상호 접속된 다수의 노드(102, 104, 106)을 포함하는 네트워크 혹은 상호접속에 대한 것이다. 각 노드의 단계는 구조 내에 노드의 위치에 따라서 결정되고 데이터 메시지는 노드에서 노드로 소오스 단계에서 목적지 단계로 이동한다. 상호 접속 구조 내의 각 노드는 다른 노드로부터 입력 포트에서 동시적인 데이터 메시지(108, 110)를 받아들일 수 있고 수신노드는 각 출력 포트를 거쳐서 각각의 수신된 데이터를 전달할 수 있으며 수신 노드의 단계보다 낮은 단계로 상호 접속 구조 내의 노드를 분리할 수 있다.

Description

복수개의 제어선을 이용한 복수 단계 최소 로직 네트워크상의 처리능력을 증가시키는 확장성 장치 및 방법{Scalable apparatus and method for increasing throughput in multiple level minimum logic networks using a plurality of control lines}
인터넷, 대형의 병렬 컴퓨터와 같은 발전된 컴퓨터 시스템 및 발전된 통신 시스템은 모두 낮은 대기시간과 높은 처리성능을 제공하면서 제어 및 로직을 절감하는 상호접속 구조를 필요로 한다.
이러한 시스템으로서 미국특허등록번호 5,996,020, 특허권자 코크 에스. 리드, 1999. 10. 30.("리드의 특허")가 있으며, 이 기술은 참고로서 기술되었다. 리드의 특허는 상호접속 구조를 통하여 통신하는 메시지의 타이밍과 위치선정에 기초하는 데이터 플로우 기법을 이용하는 네트워크와 상호접속 구조에 관해 기술하였다. 스위칭 제어는 그 구조상에 있는 여러 개의 노드들로 전파되기 때문에 전체 제어 기능을 제공하는 감시 제어기 및 복합 로직 구조는 피할 수 있었다. 이 상호접속 구조는 "편향" 또는 "곤란"한 시스템으로서 각각의 노드에 대한 그 처리 및 기억의부담은 최소화되었다. 전체 제어기 및 노드들의 버퍼링을 제거한 것은 메시지 통신에 대한 처리능력 및 낮은 대기시간을 개선시키면서 전체 제어 요소와 네트워크 상호 연결을 단순화하여 제어 및 로직 구조의 양을 매우 감소시켰다.
보다 상세하게는, 리드의 특허는 원하는 출력 포트가 가능할 때까지 패킷을 지연시키기 보다는 다른 출력 포트를 통해 메시지 패킷을 상호접속 구조상의 동일 단계에 있는 노드들로 경로를 지정함으로써 각 노드들의 처리 및 기억의 부담이 크게 감소되는 개념을 기술하였다. 이러한 개념에 의하여 각 노드에서의 버퍼들은 제거되었다.
리드의 특허에 대한 일 측면에 있어서, 상호접속 구조는 복수개의 노드들과 복수개의 상호접속 선들을 포함하며, 각 단계들은 상호접속된 링들의 집단을 포함하는 복수 단계 구조상에 있는 각각의 노드들을, 단계의 계층에 있는 복수의 J+1개의 레벨과 각 단계마다 복수의 C*2k노드들을(C는 선의 개수를 나타내는 정수) 포함하는 복수 단계 구조와 연결시킨다. 제어 정보는 데이터 상호접속 구조에서의 전송 충돌을 해결하기 위해 보내지며 각 노드는 근접한 외부 단계에 있는 노드들의 후계자(successor)이며 같은 단계에 있는 노드에게는 중간 후계자이다. 중간 선임자(predessor)로부터의 메시지 데이터는 우선순위를 가진다. 제어 정보는 야기될 충돌을 경고하기 위해 특정 단계의 노드로부터 근접한 외부 단계에 있는 노드들로 보내진다.
리드의 특허는 종래 기술에 대하여 실질적으로 진보된 것이지만, 실질적으로는"한 단계 진보"된 것으로서 메시지들은 메시지가 있는 동일 단계 또는 메시지의 최종 목적지에 근접하는 보다 낮은 단계의 어느 한 노드의 입력 포트의 가능여부에 기초하여 상호접속 구조를 통하여 전파된다. 리드의 특허에서 노드들은 각 노드의 입력 포트에서 복수개의 동시 메시지들을 받을 수 있다. 그러나, 리드의 특허에서, 들어오는 메시지가 보내져야만 하는 차단되지 않은 가능한 노드가 한 개만 있기 때문에 실제로 리드의 특허에서의 노드들은 동시의 입력 메시지들을 받을 수 없다. 리드의 특허는 또한 각 노드는 메시지의 현재 단계 보다 한 단계 아래 이상인 어느 레벨로부터의 정보를 고려해야 하는 것을 나타내며, 이로서 네트워크 상에서의 처리율을 절감시키며 대기시간의 절감을 이루는 것이다.
최적의 네트웍 구조를 이루기 위한 두 번째 시도는 존 이. 헤씨의 미국 특허출원번호 09/009,703, 1998/01/20 출원("헤씨의 특허")이 있다. 이 특허 출원은 조기진행 출원과 같은 지위로 분류되었으며, 그 기술은 본 명세서 상에 참고로서 포함하였다.
헤씨의 특허는 리드의 특허를 따라서 모든 종류의 컴퓨터와 네트워크와 통신 시스템에서의 사용을 위한 것으로 복수 단계 최소 로직 상호접속 구조의 기능성을 확장시키는 확장성을 갖는 저-대기시간 스위치에 관한 것이다. 헤스의 특허에서 설명되는 확장성을 갖는 저-대기시간 스위치를 이용하는 상호접속 구조는 네트워크로 메시지를 삽입시키는 상향된 프로시져에 의해 웜홀 경로지정을 이루는 방법을 제공한다. 확장성을 갖는 저-대기시간 스위치는 수많은 단순 제어 셀(노드)로 구성되며 이것은 배열 형태로 배치된다. 이 배열상의 많은 노드들은 단계와 컬럼으로 배치되는 배열을 가지며 특히 64에서 1024사이의 2의 제곱승이 되는 디자인 파라미터이다. 각 노드는 2개의 데이터 입력 포트와 2개의 데이터 출력 포트를 가지며, 보다 큰 단위유닛을 형성하기 위해 결합되는 "쌍-노드(paired-node)" 디자인과 같이 노드들은 보다 복잡한 디자인으로 구성된다.
헤씨의 특허의 메시지들은 배열의 외부 실린더 상에 있는 차단되지 않은 노드들로 삽입되지 않으며, 전체 메시지가 A와 B사이에 맞는다면 배열의 A 및 B 두 칼럼으로 동시에 삽입된다. 이러한 전략은 스위치 내에서 미리 어느 하나의 메시지의 첫 번째 비트가 다른 메시지의 내부 비트와 충돌되는 것을 유리하게 방지한다. 따라서, 전체 메시지들 사이의 경쟁은 상호접속 구조상에서 많은 노드들 통하여 웜홀 메시지를 보내는 바람직한 결과에 따라서 두 개의 충돌하는 메시지들의 첫 번째 비트를 해결함으로써 이루어진다.
헤씨의 특허는 실제로 종래 기술보다 진보된 것이지만, 이것 역시 실질적으로는 웜홀 경로지정을 결합시킨 "한 단계 진보"된 시스템에 불과하다. 추가적인 개선 사항들은 저-대기시간, 높은 처리율, 상호접속 구조를 제공하는 것을 가능하게 하였고 이 발명은 이러한 개선사항을 이루었다.
본 발명은 1998/01/20일에 제출된 미국특허출원 일련번호 09/009,703에 관한 것으로서, 현재 진행중이며 그 내용은 참조부호에 의해 표기하였다. 본 발명은 또한 미국특허등록번호 5,966,020에 관한 것으로서 그 내용은 참조부호로 표기하였다.
개시된 시스템 및 운영방법은 본 발명에 포함되며 아래에 기술된 출원진행중인 발명의 주제와 관련이 있다.
1. 미국 특허출원번호 (미정), 제목 "확장성을 갖는 다경로 웜홀 상호접속", 대리인번호 M8175US, 발명자 존 헤씨, 본 발명과 동일자로 출원.
2. 미국 특허출원번호(미정), 제목 "병렬 연산 및 병렬 메모리 액세스를 위한 확장성을 갖는 상호접속구조", 대리인번호 M9051US, 발명자 코크 리드 및 존 헤씨, 본 발명과 동일자로 출원.
3. 미국 특허출원번호(미정), 제목 "서비스 처리의 품질을 이용하는 확장성을 갖는 상호접속구조", 대리인번호 M9051US, 발명자 코크 리드 및 존 헤씨, 본 발명과 동일자로 출원.
4. 미국 특허출원번호(미정), 제목 "확장성을 갖는 웜홀 경로 집중기", 대리인번호 M9458US, 발명자 존 헤씨 및 코크 리드, 본 발명과 동일자로 출원.
본 발명은 컴퓨터 연산 및 통신 시스템에서의 상호접속 구조에 관한 것이다. 보다 상세하게 본 발명은 복수개의 노드를 갖는 복수 단계 상호접속 구조에 관한 것으로서 각각의 노드는 메시지를 다른 노드에 보내며, 각 노드는 복수개의 동시 입력을 받을 수 있고 소정의 메시지를 전달하는 노드보다 적어도 한 단계 아래의 레벨에 위치하는 노드들을 검사함으로써 메시지를 어디로 보낼 것인지 결정할 수 있다. 또한 본 발명은 제어 로직의 적절한 증가가 나타나더라도 종래 기술(아래에 기술)보다 대기시간이 낮은 시스템을 제공한다.
도 1 및 도 2는 본 발명에서 이용되는 상호접속 구조를 도시한다.
도 3A-3C는 본 발명에 따른 교차 노드 접속을 도시한다.
도 4는 본 발명의 이용으로서 적용 가능한 3단계의 상호접속 구조를 도시한다.
도 5는 본 발명의 상호접속 구조에서의 복수 개의 노드들의 상호접속을 도시하는 상호접속 블록도이다.
도 6A 및 7은 복수 개의 노드들 사이의 제어 및 메시지 선의 상호접속을 도시한다.
도 6B 및 6C는 상호접속 구조의 일부로서 노드들 사이의 상호접속을 도시하며 노드들중 한 노드를 통한 데이터 경로를 도시한다.
도 8은 본 발명의 일 실시예에 따른 셀 노드들의 배열을 도시한다.
따라서 본 발명의 목적은 리드의 특허와 헤씨의 특허의 장점을 이용하며 이들의 기술을 보다 개선시킴으로써 높은 처리율, 저-대기시간의 상호접속 구조를 제공하는 것을 목적으로 한다.
또한 본 발명의 목적은 기본 구조를 추가함으로써 리드와 헤씨의 특허에서 설명된 "한 단계 진보"로 개선을 하는 것이 아니라 이들 특허에서 나타난 상호접속 구조를 채택하는 것을 또 다른 목적으로 한다.
또한 본 발명의 목적은 리드와 헤씨의 특허에서의 상호접속 구조에서 설명된 것과 같이, 각 노드가 보다 효율적으로 기능함으로써 대기시간을 줄이고 메시지 처리율을 증가시키는 것을 또 다른 목적으로 한다.
또한 본 발명의 목적은 각 노드가 메시지를 차단하지 않고 노드 입력 포트에서 동시성 메시지들을 수용하도록 함으로써 리드와 헤씨의 특허의 상호접속 구조를 개선시키는 것을 또 다른 목적으로 한다.
또한 본 발명의 목적은 "복수의 단계가 진보된" 시스템을 제공하는 것으로서, 어느 한 노드는 메시지가 특정의 노드로 입력되는 그 레벨의 아래에서 한 레벨 이상의 레벨에 있는 다른 노드들에 관한 제어 정보를 받도록 하는 것을 목적으로 한다.
본 발명의 바람직한 실시예에 의하면, 상호접속 구조는 계층적 복수 단계 구조상에서 노드들을 각각 연결시키는 복수개의 노드들과 복수개의 상호접속 선들로 구성된다. 그 구조상에서 어느 한 노드의 단계는 그 구조 내에 있는 노드의 위치에 의해 정해지며, 그 구조 내에서 데이터는 출발지 단계에서 목적지 단계 또는 아래에 있는 복수 단계 구조의 어느 한 단계로 이동한다. 데이터 메시지는 출발지 노드로부터 복수개의 목적되는 목적지 노드중 어느 하나로 복수 단계 구조를 통하여 전송된다.
본 발명의 특성은 상기 복수개의 노드들에 포함된 각 노드는 복수 개의 입력 포트 및 복수 개의 출력 포트를 갖는 것이며, 각 노드는 2개 또는 그 이상의 입력 포트에서 동시성 데이터 메시지들을 수신할 수 있는 것이다.
본 발명의 또 다른 특성은 상기 상호접속 구조 내에서 출력이 각각의 노드들을 향한다면 노드는 상기 수신된 데이터 메시지들의 각각을 분리된 노드들을 통해 전달할 수 있으며, 각 노드는 동시성 데이터 메시지들을 수신할 수 있는 것이다.
본 발명의 또 다른 특성은 상호접속 구조 내의 어는 한 노드는 데이터 메시지들을 수신하는 그 노드 아래로 한 단계 이상의 노드들에 대하여 정보를 수신할 수 있는 것이다.
본 발명에서 전술한 목적 및 특성과 더불어 기타 목적 및 특성은 첨부한 도면과 함께 이하 실시예에서 더욱 자세하게 이해될 것이다.
본 발명은 미국 특허등록번호 5,996,020("리드의 특허")와 미국 특허출원번호 09/009,703, 1998/01/20 출원("헤씨의 특허")에서 개시된 상호접속 구조를 참조부호로서 포함한다. 리드의 특허에서 노드들은 원통형 형태로 배열되었으며, 헤씨의 특허의 노드들은 행 및 열로 배열되었다. 양자의 특허 모두 본 발명의 상호접속 구조에서 사용될 수 있는 노드 환경의 다양한 형태에 관하여 설명하고 있다. 리드와 헤스의 특허 모두, 상호접속 구조 및 노드 환경면에서, 본 발명에 적용될 수 있다.
도 1을 참조하면, 리드의 특허에서 설명된 것과 같은 상호접속 구조가 도시된다. 도 1에는 세 개의 노드들이 있다. 두개의 노드 A(102), B(104)는 세 번째 노드 C(106)에 직접 메시지를 보내기 위하여 위치하고 있다. 노드 B 및 C는 네트워크의 단계 N에 있고 노드 A는 네트워크의 단계 N+1에 있다. 리드와 헤씨의 특허에서 설명된 바와 같이, 노드 B는 노드 C로 데이터를 보내는 데에 있어서 노드 A보다 우선 순위를 갖는다. 노드 B가 경로(114)를 통해 노드 C로 메시지 MB를 보낼 때, 노드 B는 노드 A에게 MB를 C로 보내는 것을 알리는 제어신호(120)를 보내기 때문에 메시지 MB와 충돌을 일으킬 수 있는 단위 시간 동안에는 A는 메시지 MA를 C로 보내지 않는다. 만약 MA의 헤더에 의해 지시되어 C로부터 MA의 출력인 목적지로 경로가 존재하고 B에서 A로 제한신호가 존재하지 않으면 A는 경로(112)를 따라 MA를 C로 경로지정 한다. 이러한 조건들이 모두 유지되지 않으면, A는 MA를 C가 아닌 네트워크의 N+1 단계에 있는 다른 노드(도시하지 않음)로 보낸다.
리드의 특허에서는, 노드 A 및 노드 B는 서로 다른 실린더 상에 있는 동일 각도에 위치하게 된다. 헤씨의 특허에서는, 노드 A 및 B는 서로 다른 단계의 동일 컬럼상에 있게 된다.
도 2에는 4개의 노드들이 도시되어 있다. 노드 B, C 및 D는 네트워크의 N단계에 있고 노드 A는 네트워크의 N+1단계에 있다. 노드 B로부터 연장되는 네트워크상의 모든 출력 포트는 노드 C 및 노드 D로부터도 연장될 수 있다. C로부터 연장될 수 없는 A로부터 연장되는 출력포트가 있다. 이 때문에, A에서 C로 메시지가 전달될 때 메시지가 도달하는 출력포트의 세트는 좁아진다. 네트워크 상의 노드들 중에서, 노드 C는 노드 D와 같은 단계에 있지만 노드 C가 노드 D로 메시지를 보내는 데에 있어서 가장 높은 우선 순위를 가진다. 이러한 이유로, 한 개의 메시지 M이 주어진 단위 시간에 노드 C에 도착하면, 메시지 M은 노드 D로 갈 수 있으며, D로부터 M의 목적된 출력포트로 경로가 존재한다. 그러므로, 노드 C에서 버퍼를 가질 필요는 없으며, 동일한 이유로 버퍼들은 다른 노드에서도 사용되지 않는다. 리드와 헤스의 특허에 있어서, B가 C로 충돌 메시지를 보내지 않을 것이라고 노드 A에 연계된 로직이 통보 받지 않으면 메시지 MA는 A에서 C로 갈 수 없다. 노드 C로 데이터를 보내는 노드 A에 대한 노드 B의 우선 순위는 B에서 A로의 제어신호에 의해 강화된다. 이러한 방법으로, A가 MA를 C로 보내기를 "원하고" B에서 A로의 제어신호에 의해 A는 MA를 C로 보내는 것이 제한되지 않는다면, A는 MA를 C로 경로지정 한다. 도 2에서는 리드와 헤씨의 특허에서 설명된 바와 같은 네트워크의 일부, 또는 "확장성 있는 복수경로 웜홀 상호접속" 특허 출원을 도시하며, C로부터 MA의 헤더상에 있는 MA의 목적지 출력 포드로 경로가 존재한다면 노드 A는 MA를 C로 보내길 "원한다". 도 2에는 "확장성 있는 웜홀 경로지정 집중기" 특허 출원에 있는 상호접속 구조의 일부분이 도시되며, 집중기의 경우, 모든 출력은 MA에 대한 수신 가능한 출력 포트이기 때문에 노드 A는 항상 MA를 C로 보내길 "원한다". 선택적으로 헤씨의 특허는 노드 B를 거침으로써 C로 가기 위해 A로부터 C로 메시지를 허용하면서 주어진 시간에 한 개의 메시지만이 노드 C로 도착한다는 사실을 이용하였다.
노드 3A를 참조하면, 리드의 특허에서 설명된 상호접속 구조의 일부가 도시된다. 리드의 특허는 특정 단위 시간동안 오직 한 개의 메시지만이 C로 들어간다. 반면에, 본 발명에서는, 아래에 설명한 바와 같이, 2개의 동시성 메시지들이 노드 C로 들어가는 것이 가능하기 때문에 A로부터 C 및 B로부터 C로의 메시지들은 동시에 노드 C로 들어가는 것이 가능하다.
도 3B는 헤씨의 특허에서 이용되는 상호접속 구조의 일부를 도시한다. 데이터 경로(306)는 A 또는 B로부터 메시지를 받아들이고 C로 오직 한 개의 메시지를 전달할 수 있다. 도 3B의 노드들은 도 3C에서 도시된 것처럼 노드 B에서 노드 C까지의 추가 경로(316)로 변경될 수 있으며, 따라서 노드 A 및 B 는 모두 C로 전송할 수 있다. 도 3B의 노드 A는 C로 보내기 위하여 데이터 경로 304 및 306을 이용한다. 도 3C의 노드 A는 C로 보내기 위하여 데이터 경로 314 및 316을 이용한다. 그러나, 리드의 특허처럼 헤씨의 특허도 특정 노드가 두 개의 동시성 메시지를 받아들이도록 허용하지 않았으나 본 발명에서는 가능해 진다. 본 발명의 진보는 3B의 실시예를 3C의 실시예로 변경함으로서 리드 및 헤씨 구성에 쉽게 적용될 수 있다.
도 4는 본 발명의 제 1 실시예를 도시한다.
다섯 개의 노드가 도 4에 도시되어 있다. 도 2에 개시된 네 개의 노드에 덧붙여, 단계 N-1 에 노드 H 가 존재한다. 노드 C는 노드 H에 데이터를 전송할 수 있다. 노드 B가 메시지 MB를 C로 전송하고 이 메시지를 C로부터 H 로 이송할 때, 노드 A 는 메시지 MA를 C로 전송할 수 있으며 메시지 MB와 동시에 C에 도달하게 된다. MB가 C로부터 H로 이동하는 동일한 시간동안 메시지 MA는 C로부터 D로 이동한다. 동시에 두 메시지를 수용하는 노드의 능력은 본 발명의 특징으로, 이전의 리드 및 헤씨 특허를 능가하는 새로운 진보이다.
노드 C에 버퍼가 없기 때문에, 두 메시지 MA 및 MB가 동시에 C 에 도달할 때, 두 메시지 중 하나는 H로 이동해야하고 두 메시지중 다른 하나는 D로 이동해야 한다. 본 실시예에서, MB는 MA를 D로 이동하도록 허용하면서 H로 제한 없이 이동한다. 두 메시지 MA 및 MB 모두가 C로 이동하는 경우, C의 로직(logic)은 MA 와 MB중 하나를 H로 전송하고 MA 와 MB중 다른 하나는 D로 전송한다. 한가지 방법은 노드 C 가 MB를 C로부터 H로 보내고, MA를 C로부터 D로 보내는 것이다. 이러한 방법은 언제나 가능하기 때문에 간단하고, B 가 구조상 A보다 낮은 단계에 있기 때문에 MB는 아마도 구조상 MA보다 더 길다. 다른 실시예에서, C에 의한 메시지의 경로지정은 서비스의 질(QOS, quality of service)에 좌우될 수 있다. 이러한 실시예에서, 헤더의 일부는 서비스 정보의 질을 포함하며, MA 및 MB 가 C로 이동할 때 MA의 QOS 단계가 MB의 QOS단계 보다 높지 않는 한, C는 MB를 H로, MA를 D로 경로지정하게 되며, 이 경우 도 6C에서 도시된 바와 같이 C는 MA를 H로, MB를 D로 경로지정하게 된다. 이러한 방식에서, QOS의 보다 높은 단계를 가진 메시지가 QOS의 보다 낮은 단계를 가진 메시지를 능가하는 우선순위를 얻을 수 있다.
리드 및 헤씨 특허에서, 제어 신호(120)(도 1)는 A가 C로의 메시지 전송을 보내는 것에 대하여 차단될 것인지를 알려주면서 노드 B로부터 A로 전송된다. 이러한 차단은 B가 C로 메시지를 전송하지 않는다면 일어나지 않게 보장받게된다. 리드 및 헤씨의 특허에서 A는, 만일 동일한 시간에 B 가 C로 메시지를 보낸다면, C로 메시지를 전송하도록 하락되지 않는다. 본 발명에서 A는, B가 C로 메시지를 보내는 동일한 시간에 C로 메시지를 보내는 것이 가능한데, 만일 B로부터 C 까지 메시지가 C로부터 D까지의 선을 사용하지 않는 것이 보장되고 대신 C로부터 H 까지의 선을 사용한다면, 가능하다. (도 4 참조)
노드 A와 결합된 로직(logic)은 메시지 MA를 노드 C로 경로지정 하는 것이 가능하다. 적어도 하나의 추가 노드 N (도시 안됨)이 존재함으로서 노드 A와 결합된 로직은 MA를 N으로 경로지정 하는 것이 가능해 진다. A 가 MA를 C로 경로지정 하는 경우, 노드 C와 결합된 로직은 MA를 노드 D 및 H로 경로지정 하는 것이 가능하다. 이러한 방식에서, 메시지 MA는 A로부터 D로 이동할 수 있고 메시지 MB는 B로부터 H로 이동할 수 있다. A와 결합된 로직은 MA를 D 또는 H 어느 하나로 이동할 수 없다. 이와 유사하게, B와 결합된 로직은 메시지 MB를 B로부터 C로 전송할 수 있고, C와 결합된 로직은 MB를 노드 D 또는 노드 H 중 하나로 이동할 수 있다. 따라서 메시지 MB가 B로부터 D로, 또는 B로부터 H로 이동할 수 있는 반면, 노드 B 와결합된 로직은 메시지 MB를 노드 D 또는 노드 H 중 하나로 경로지정 할 수 없다.
도 5는 헤씨 특허에서 개시된 네트워크의 일부를 도시한 블록도이다. 노드는 배열 안에 정렬되어 있다. 노드 배열은 행렬로 배치되어 있다. 가장 오른쪽 열의 노드 배열은 동일한 단계에서 가장 왼쪽의 노드 배열에 후방으로 연결됨으로서, 예를 들면, J-1단계의 K-1열의 출력 B는 J-1단계의 0열의 입력 B를 형성한다. 도 4에서, 노드 A는 M열의 N+1단계에서 배열 안에 있는 노드이고, B는 M열의 단계 N의 노드 배열 안에 있고, C는 M+1열의 단계 N에 있는 노드 배열 안에 있고, D는 M+2열의 단계 N 에 있는 노드 배열 안에 있으며, H는 M+2열에 단계 N-1 의 노드 배열 안에 있는 노드이다. 도 1, 2, 3, 4, 6, 7 및 8은 도 5에 도시된 노드 배열의 구성원(members)들인 개별적인 노드들 사이의 연결을 보여준다.
여덟 개의 노드들이 6A에 도시되어 있는데, 이들은 본 발명의 다른 실시 예를 보여준다. 도 4의 다섯 개의 노드에 덧붙여, 단계 N에 추가적인 노드 E, 단계 N-1 에 두 개의 추가 노드 F 와 G가 존재한다. E는 G 로 메시지를 전송할 수 있고, F 는 G로, G는 H로 메시지를 전송할 수 있다.
리드 특허의 바람직한 실시예에서, 노드는 헤더(header)에서 단지 하나의 어드레스 비트(address bit)만을 판독한다. 노드 B에서 메시지 MB를 살펴보고 B가 MB를 C로 전송한다고 가정해 보자. B와 C 가 동일한 단계이기 때문에 C는 B가 판독하는 MB의 동일한 헤더 어드레스 비트를 판독하게 된다. 네트워크의 형태(topology)는 마치 B의 로직이 H 가 MB의 목적지로 향한 경로 상에 있는지를 결정할 수 있는 것과 같다. 이것은 MB의 목적지를 향한 경로 상에 H 가 있는지 여부를 MB의 단일어드레스 비트가 결정하기 때문이며, 이러한 어드레스 비트가 노드 B를 위한 로직에 의해 준비된 것과 동일한 비트이기 때문이다. 또한 MB가 C에 도달할 때, 노드 C를 위한 로직에 의해 읽혀지게 되는 것 역시 동일한 비트이다. 만일 H 가 MB의 목적지를 향한 경로 상에 있다면, MB가 도달하는 동일한 시간에 H 에 도달하는 MB와 다른 메시지는 존재하지 않으며, 도 6B에서 도시된 것처럼, MB는 일단 B로부터 C로, 그 다음 C로부터 H로 이동하게 된다. MB가 도달하는 것과 동일한 시간에 H에 도달하는 메시지는 E 또는 F 중 하나로부터 와야만 한다. 만일 E 또는 F로부터 도달하는 그러한 메시지 M이 존재하지 않는다면, MB 가 B로부터 C로, 그리고 C로부터 H로 이동하게 된다는 것은 확실하다.
F로부터 G로 이동하는 메시지가 있는지를 나타내는 F에서 E 까지의 제어 신호선(604)이 이미 존재한다. 리드 및 헤씨 특허에서는 찾아볼 수 없으나 본 발명에서 개시되고 있는 것으로 E에서 A까지의 추가적인 제어선(602)이다.
A 에서의 로직은 다음과 같이 작동한다. 메시지 MA는 노드 A에 도달한다. 노드 A는 MA의 하나의 헤더 비트를 판독한다. 만일 헤더 비트가 C에서 MA의 목적지까지의 경로가 존재한다고 나타내는 경우, 아래의 조건에 따라서 A는 MA를 C로 전송할 것이다.
1) B에서 C로 전송된 경쟁적인 메시지가 존재하지 않는다. 또는
2) C에 MA가 도달하는 것과 동일한 시간에 C에 도달하게 될 메시지MB가 존재하고, C에서 D까지의 링크를 쉽게 이용하지 않고 메시지 MB가 C에서 H로 이동하는 것이 보장된다.
B에서 A까지의 제어 신호는 B가 C로 메시지를 보내는지 아닌지 나타내고 또한 H에서부터 MB의 목적지 출력 포트(target output port)까지의 경로가 존재하는지를 나타내 준다.
F에서 E 까지의 제어 신호는 F 가 G로 메시지를 전송하는지 아닌지 나타낸다. E에서 A까지의 제어 신호는 E 또는 F중 하나가 G로 메시지를 전송하는지 아닌지 나타낸다. 노드 A는 MA를 어디로 전송할 것인지 결정하는데 필요한 모든 정보와 함께 유리하게 제공된다. 특히,
1) B에서 A까지의 제어 신호가 B에서 C로 전송되는 경쟁적인 메시지가 없다고 나타내는 경우, 그리고 C에서 MA의 목적지까지의 경로가 존재하며, A가 C로 MA를 전송하게 되는 경우, 또는
2) 다음과 같은 조건이 충족되어, A가 C로 MA를 전송하게 되는 경우,
ㆍB에서 A까지의 제어 신호가, B에서 메시지 MB가 존재하며 H에서 MB의 목적지 출력까지 경로가 있다고 나타내 주고,
ㆍE에서 A까지의 제어 신호가, E에서 G로 또는 F에서 G로 전송되는 경쟁적인 메시지가 없다고 나타내고, 노드 A가 MB를 위한 C에서 D 까지의 경로를 사용하지 않고 MB가 C에서 H로 이동할 것이라고 판단하고,
ㆍC에서 MA의 목적지 출력 포트까지 경로가 존재한다.
3) 아니면, A가 A와 동일한 단계에 있는 C와 다른 노드(도시 안됨)로 MA를 전송한다.
두 메시지 MA 및 MA' 가 동시에 노드 A에 도달하는 경우, 두 메시지 중 하나는 상기 로직에 따라서 C로 전송되고, 남은 메시지는 C (도시 안됨)와 다른 노드로 전송된다. 이러한 방식에서, 리드와 헤씨의 특허에서는 단계를 떨어뜨리지 못하나 본 발명에서는 유리하게 단계를 떨어뜨리는 메시지가 존재한다. 상기 로직의 특징은 어느 두 메시지든 동시에 노드에 도달하면 적어도 이들 메시지 중 하나는 보다 낮은 단계로 떨어질 수 있게 된다는 것이다.
복수 비트(multi-bit) 메시지는 버퍼링 없이 노드 A를 통과한다는 것에 주목하자. 고정된 최대 시간 T 가 있고 노드 A에 도달하는 어떤 메시지든 노드 A에 도착하는 시간 T 안에 노드 A를 떠날 것이다. 또한 선(602) (도 6A)에 의해 전달되는 제어 정보가 노드 E 및 F를 통해 메시지 전송에 관계하고, 따라서 노드 A에 도달하는 메시지에 의해 결정되지 않는다는 점이 중요하다.
도 7은 도 6A와 동일한 노드를 가지지만, E에서 A까지의 제어선 대신에 F에서 B까지의 제어선 CFB 와 E에서 B까지 추가 제어선 CEB를 가진다. 제어선 CFB 는 F에서 B로 단일 비트 x 의 형태로 정보를 전송한다. F에서 로직이, B에서 H로 이동하는 메시지와 동일한 시간에 H 에 도달할 수 있으며 F에서 G로 전송된 메시지가 없다고 판단된다면 비트 x 는 제로로 설정된다.
1) F에서 G로 송부된 메시지가 없거나 또는
2) F에서 G로 전송된 메시지가 G에서 H와는 다른 노드 J (도시안됨)로 전송된다면, F는 x를 제로로 설정할 수 있다.
E에서 B까지의 제어선 CEB 는 단일 비트 y의 형태로 정보를 전송한다. 만일 E가, B에서 H로 이동하는 메시지와 동일한 시간에 H에 도달할 수 있는 메시지를 E에서 G로 전송하지 않는다면, 비트 y는 제로로 설정된다.
노드 B는 메시지를 어디로 전송할 것인지 판단하기 위해 비트 x 및 y 에 포함된 정보를 이용하지 않는다. 그 자신의 메시지를 어디로 전송할 것인지 판단하기 위해 단계 N-1(도시 안됨)에서 한 개 노드의 또 다른 제어선으로부터 오는 정보를 이용한다. 노드 B는 제어선 CBA를 이용하여 A로 제어 신호를 보낼 수 있도록 하기 위하여 선 CEB 와 CFB 의 정보를 이용한다. 노드 B는 제어선 CBA에서 단일 비트 z를 전송한다. 정확하게 하나의 메시지 MA가 노드 A에 도달하는 것으로 추정된다. MA는 비트 z가 제로이고 C가 MA의 목적지 경로에 놓여 있다면 노드 A에서 C로 전송된다.
1) B가 A로부터 오는 메시지 MA와 충돌을 일으킬 수 있는 시간에 B에서 C로 메시지를 전송하지 않거나, 또는
2) B 가 x 및 y, 그리고 MB의 헤더 안에 포함된 정보를 근거로 메시지 MB를 C로 전송하고, B에 있는 로직이 C에서 H로 MB가 이동할 것이 확실하다고 판단한다면,
비트 z는 제로로 설정된다.
노드 A는 MA의 헤드 및 단일 비트 z의 값(value)을 근거로 들어오는 메시지 MA를 전송할 수 있다. 두 메시지 MA 및 MA' 가 동시에 A에 도달하는 경우, 이 둘 중 하나의 메시지는 상기 로직에 따라 C로 전송되고, 다른 메시지는 C(도시 안됨)와 다른 노드로 전송된다. 상기 로직의 특징은 두 개 메시지 MA 와 MA'중 하나는 C로 떨어지는 것이 가능해 진다는 것이다. 특히, 메시지 MA 및 MA'는 A의 동일한 출력 포트로 경로지정되지 않는다.
본 실시예에 따른 노드는 하나의 헤더 어드레스 비트 및 보다 낮은 단계로부터의 제어 비트를 근거로 메시지를 전송할 수 있다는 점이 중요하다. 이런 방식에서 시간은 리드 및 헤씨 특허에서의 시간과 동일하다. 중요하게 도 7의 실시예에서, 도 6A의 로직을 이용하는 노드 A가 메시지를 C로 전송할 수 없었고 대신에 단계 N+1에서 노드로 메시지를 전송했을 경우에, 노드 A는 C로 메시지를 보낼 수 있다.
리드 및 헤씨의 특허에서, 그리고 이들 특허에서 이제까지 묘사되었던 기술내용에서, 노드는 메시지가 존재하는지를 나타내는 헤더의 비트를 판독하고, 추가적인 헤더 어드레스 비트를 판독한다. 또한 서비스 비트의 질(quality)과 같은 추가적 비트를 판독할 수 있다. 본 발명의 또 다른 실시예에 따르면, 노드는 복수개의 어드레스 비트(multiple address bits)를 판독할 수 있다.
도 6A와 관련하여, 다른 실시예에서, 노드는 메시지 헤더에서 두 개의 어드레스 비트를 판독한다. 단일 메시지 MA가 H를 포함하는 목적지 경로로 A에 도달하는 경우, 그리고 메시지 MB가 H를 포함하지 않는 목적지 경로로 B에 도달하고 여기서 B는 MB를 C로, 이어서 D로 보내야만 하는 경우를 생각해 보자. 도 6A(그리고 그 이전의 도면들)에서 보여진 구조는 노드 C에서 메시지 MA가 메시지 MB를 교차하도록(cross over) 허용하는데, 도 6C에서 도시된 것처럼 MA의 경로는 노드 A, C 그리고 H를 통해 가고, MB의 경로는 노드 B, C 그리고 D를 통해 간다. 이러한 실시예의 목적은, 메시지 MA가 동일한 시간에 공통의 노드 C를 통해 지나가는 경쟁적인메시지 MB를 교차하도록 허락되는 때를 결정하는데 필요한 정보를 노드에 제공하는 것이다. 메시지 MA는, MA의 목적지를 향한 C를 통과하는 경로가 있는지 아닌지를 나타내는 하나의 헤더 비트를 판독하는 노드 A에 도달한다. 노드 A는 또한 MA의 목적지를 향한 H를 통과하는 경로가 있는지를 나타내는 추가적인 헤더 비트를 판독한다. E로부터 A까지의 제어 신호는, E 또는 F로부터 메시지가 MA와 동일한 시간에 H에 도달하지 않을 것이라는 것을 보장해 준다. B부터 A까지의 제어 신호는 메시지 MA와 동일한 시간에 C에 도달하게 될 메시지 MB가 B에 있는지를 나타내는데, 만일 그렇다면, MB가 H를 통해 지나가지 않는지 나타낸다. 이러한 제어 신호를 근거로, 노드 A는 다음과 같은 조건들 중 적어도 하나가 만족된다면 메시지 MA를 C로 보낸다.
1) C부터 D까지의 경로가 자유로운 것으로 알려지면, MA의 목적지를 향한 C를 통과하는 경로가 존재한다.
2) C부터 H까지 경로가 자유로운 것으로 알려지면, MA의 목적지를 향한 H로부터의 경로가 존재하고, H에 MA가 도달하는 것과 동시에 H에 도달할 수 있는 E 또는 F로부터의 메시지는 존재하지 않는다.
상기 제 1 조건(1)은 위에서 논의된 것이며, 제 2 조건은 교차 (cross over) 경우에 속한다. 만일 상기 조건들 모두가 만족되지 않는다면, A는 MA를 C와 다른 노드(도시 안됨)로 전송하게 되고, 이러한 노드는 단계 N+1에 있게 된다. 두 메시지 MA 및 MA'가 동시에 노드 A에 나타나게 되는 경우는 상기 설명된 바와 같이 다루어진다. 두 개 헤더 비트를 판독하는 것은 상기 조건 (2)를 탐지하도록 허용한다. 때로는 도 6A의 보다 앞선 실시예 하에서 A와 동일한 단계에 머물러야 하는, A에서 C로 메시지 MA의 전송을 허용한다. 두 개 헤더 어드레스 비트의 판독은 여기서 그리고 리드 및 헤씨 특허에서 설명된 네트워크의 제어 로직 및 제어 신호들에 대한 단지 약간의 변경을 요구한다. 이러한 변경은 본 발명의 기술 분야에 통상의 기술을 지닌 이에게는 자명한 것으로, 이러한 변경에 대한 상세한 설명은 여기서는 생략하기로 한다.
도 7에서, 노드 A는 노드 C를 통해 노드 H로 데이터를 전송할 수 있으며, 한편 노드 F는 노드 G를 통해 노드 H로 데이터를 전송할 수 있음에 주목하자. 제어 신호 x 및 z 는 A부터 H 까지의 데이터 전송에 대한 F부터 H 까지의 데이터 전송의 우선 순위를 실행한다.
도 8과 관련하여, 노드 A 및 H는 칼럼 K+2의 단계 N-1에 존재한다. 칼럼 K+1의 단계 N에 있는 노드 B 와 C는 A와 H로 직접 데이터를 전송하도록 위치된다. 칼럼 K의 단계 N+1의 노드 U와 V는 직접 B로 데이터를 전송할 수 있고, 칼럼 K의 단계 N+1의 노드 W 와 X는 C로 직접 데이터를 전송할 수 있다. 노드 B는 단계 N의 노드 D로부터 직접 데이터를 받고 단계 N의 노드 L로 직접 데이터를 보낸다. 노드 C는 단계 N의 노드 E로부터 직접 데이터를 받고 단계 N의 노드 M으로 직접 데이터를 보낸다. 칼럼 K에 있는 노드의 집합 R은 도 8에 도시되지 않았는데, R의 구성원(members)은 노드 D와 E로 제어 신호를 전송할 수 있다. 노드 D는 R(도시 안됨)에 있는 노드로부터의 정보를 이용하고 노드 E는 노드 D로부터의 동일한 정보를 이용한다. 노드 D가 R에 있는 노드로부터 받는 제어 정보는, 노드 B로부터 노드 A및 H 까지의 경로들이 차단되지 않았는지 노드 D가 판단하는 것을 가능하게 한다.
도 8은, 주어진 단계 N에서 각각의 노드 C가 단계 N+1에서 두 개 노드로부터 그리고 단계 N에서 한 개 노드로부터 데이터를 수신하도록 위치되며, 또한 단계 N-1에서 두 개 노드로 그리고 단계 N에서 한 개 노드로 데이터를 전송하도록 위치되는 데이터 상호접속 구조의 일부를 도시한다. 이러한 데이터 상호접속 구조와 네트워크는 다음 단계 구성(Next Level Embodiment)에 대한 다중 상호접속(multiple interconnection)처럼 리드 특허에, 그리고 단순 대기시간 구성(Flat Latency Embodiment)처럼 헤씨 특허에 언급되어 있다. 제어 상호접속은 리드 및 헤씨의 특허에 개시되어 있으며, 본 특허는 이들 특허의 개시 내용을 참조로 하고 있다.
본 발명에 있어서, 데이터 상호접속 구조는 리드와 헤씨 특허에서 기술된 바와 같지만, 노드는 훨씬 정교하게 되어 있어서 처리능력을 증대시키고 적은 대기시간을 얻기 위해서 보다 많은 제어정보를 받아들이고 처리한다. 노드는 버퍼되어 있지 않기 때문에, 노드로 들어가는 메시지는 노드를 즉시 떠날 수 있어야 하며 목적지 출력으로 향하는 다른 노드로 진행되어야 한다. 두 개의 메시지가 노드를 떠날 때마다 하나는 동일 단계를 따라서 계속하고 다른 하나는 하나의 단계를 떨어뜨려야 한다. 교정된 동작은 제어 신호에 의한 우선 순위 규칙에 따른다. 각각의 노드가 단지 하나의 목표 헤더 방향 비트를 읽는 단순한 경우를 고려하게 될 것이다. 이러한 사실은 단계 N에 대한 어떤 노드도 단계 N+1에 대한 노드로부터 나온 두 개의 메시지를 동시에 받아들이지 않는다. 또한, 단계 N 노드가 두 개의 메시지를 받아들이는 경우에, 동일한 단계 N에서부터 도달하는 메시지는 단계 N-1에 대한 노드로 떨어지게 될 수 있고 항상 그렇게 될 것이다.
노드 B는 노드 A 및 H에 데이터를 보내는 데에 있어서 노드 C보다 우선 순위를 가진다. 노드 D는 노드 B에 데이터를 보내는 데에 있어서 노드 U 및 V보다 우선 순위를 가진다. 마찬가지로, 노드 E는 노드 C에 데이터를 보내는 데에 있어서 노드 W 및 X보다 우선 순위를 가지고, 노드 W는 노드 C에 데이터를 보내는 데에 있어서 노드 X보다 우선 순위를 가진다. 본 발명에 따른 다른 실시예에서와 마찬가지로, 주어진 시간에서, 제어 신호는 컬럼 K에 대한 노드로부터 노드 D 및 E로 들어간다. 노드 D로 들어가는 가능한 메시지와 노드 D가 받아들이는 제어신호에 근거하여, 노드 D는 노드 B로 메시지를 보낼 수도 있고 그렇지 않을 수도 있다. 적당한 시간에, 노드 D는 제어신호를 노드 U 및 E로 보내고, 이러한 사실은 1)어떤 메시지도 노드 D로부터 노드 B로 보내어지지 않았다; 2)메시지 MD는 노드 B로 전해졌고, MD가 노드 B에 도달하면, 노드 B는 MD를 노드 A로 향하게 한다; 3)메시지 MD는 노드 B로 전해졌고, MD가 노드 B에 도달하면, 노드 B는 노드 H에 메시지 MD를 보낼 것이다; 혹은 4) 메시지 MD가 노드 B에 보내졌고, 메시지 MD는 노드 B에서 노드 L로 가게 될 것이라는 의미중의 어느 하나를 지시한다. 1, 2 및 3의 경우에, 노드 U에서 MU에 메시지가 있으며 MU는 노드 B를 거쳐서 목적지에 도달하면, 메시지 MU는 노드 B로 전해지며, 노드 V로부터는 어떤 메시지도 노드 B로 가지 않게 된다. 상기 1, 2 또는 3의 경우가 유지된다면, 노드 U는 노드 B로 메시지를 전달하지 않으며, 노드 V는 노드 B로 메시지를 전달하기 위하여 요청(invited)된다. 즉, 노드 U가 노드 B로 메시지를 보내지 않으면, 노드 U는 제어신호로서 노드 V에 그렇게 알리고, 노드B를 통해서 목적지에 도달하는 노드 V에 메시지 MV가 있으면, 노드 V는 노드 B에 MV를 보내게 될 것이다. 경우2에서, 이미 검토된 싱글 다운(single down) 경우에서와 같이, A에서 MD의 도착과 충돌을 일으키는 시간에 다른 메시지가 A에서 도착하지 않을 것이고 A에서 MD의 목적지 출력 포트로 경로가 있다는 정보에 기초해서 노드 B가 메시지 MD를 A로 경로지정 할 것을 노드 D는 예측할 수 있다. 유사한 상황이 경우 3에 존재한다. 본 발명에 있어서, 경우 2와 3이 유지되고, U 혹은 V가 B로 메시지를 보내면, B는 두 가지 메시지를 받을 것이다. 이것은 주어진 시간 동안에 단지 하나의 메시지만 B로 전달되는 리드와 헤씨 특허와 대비된다.
노드 E로 들어가는 가능한 메시지와 E가 받아들이는 제어신호에 기초해서, E는 노드 C에 메시지를 전달할 수도 있고 그렇지 않을 수도 있다. D로부터 나와서 E로 향하는 제어신호는 노드 E에 의해서 메시지의 경로지정에 영향을 주지 않지만, E가 노드 W로 보내는 제어신호에 영향을 줄 수 있다. 적절한 시간에, 노드 E 와 관련된 로직은 다음 조건 중의 어느 하나를 유지하고 있음을 확인한다: 1) E는 노드 C에 어떠한 메시지도 보내지 않는다; 2) E는 메시지 ME를 노드 C에 보내고 ME가 C에 도달하면, C는 ME를 A로 보낼 것이다; 3) E는 메시지 ME를 C로 보내고 ME가 C에 도달하면, C는 ME를 H로 보낼 것이다; 4) E는 메시지 ME를 C로 보내고 C가 ME를 노드 M으로 경로지정할 가능성이 존재한다. D로부터 E로 가는 제어신호는 C에 의해서 ME의 경로지정을 예측하기 위해서 C와 관련된 로직에 의해서 사용된다. 이것은 노드 A로 경로지정 하는데 B와 C가 동시에 허용되지 않고 노드 H로 경로지정 하는데 B와 C가 동시에 허용되지 않기 때문이다. 조건 1, 2, 3이 유지되면, 노드 E는 노드C로 경로지정 하기 위한 W 허가를 주는 노드 W로 비-차단 제어신호를 보낸다. 경우4에서, 노드 E는 노드 W로 차단 제어신호를 보내고 W는 X로 차단 제어신호를 보내며 W나 X 모두 C에게 메시지를 보내지 않는다. 노드 W가 E에서 나오는 비-차단 제어신호를 받고 W가 교정된 시간에 메시지 ME를 받아서 MW의 목적지로 C를 통해서 경로가 있다면, W는 C에 MW를 보낼 것이며 X가 C로 메시지를 보내지 못하게 하는 차단 제어신호를 X에 보낼 것이다. 노드 W가 E로부터 비-차단 제어신호를 받고 W는 C로 메시지를 보내지 않으면 W는 X로 비-차단 제어신호를 보낼 것이다. W로부터의 비-차단 제어신호가 있는 경우에, X가 적절한 시간에 메시지 MX를 받고, C로부터 MX의 목적지 출력으로 경로가 있으면, X는 C에 MX를 보내게 될 것이다.
리드와 헤씨 특허에서는 본질적으로 앞으로 한 단계를 내다보았다. 본 발명에서 제시된 두 가지 실시예에서는 앞으로 두 단계를 내다본다. 당업자에게 있어서 여기에 개시된 기술을 사용하여 앞으로 더 내다볼 수 있다.
여기서 몇 가지 트레이드 오프(trade-off)가 있다. 노드가 보다 복잡해지므로, 단계당 처리능력은 증가되고, 구조를 통한 전체 평균 단계는 감소되며, 칩 상에 위치하는 노드의 수는 감소되고 단계당 시간은 증가될 수 있다. 헤씨 특허는 유효 로드를 운반하는 광학 스위치를 구동하는 헤더를 나르는 헤더를 전자 스위치의 디자인을 개시하여 주었다. 본 발명은 헤씨 특허에서 개시된 상기 스위치를 수행하는 대체수단으로서 사용될 수 있다.
출원 번호(미정), "확장성을 갖는 다중경로 워엄홀 상호 접속" 대리인 문서번호, M8175US, 발명자 존헤씨, 동일자 출원된 미국 특허출원은 메시지 헤더에 서비스 정보의 품질을 효율적으로 사용할 수 있는 방법을 알려 주었다. 상기 미국특허출원(번호미정)의 내용은 여기에 참고로 결합되어 있다. 상기 특허 출원에 개시된 기술은 본 발명에 효율적으로 적용될 수 있고, 예를 들면, 노드 D에서 나온 제어신호는 노드 U 및 V에 노드 U 및 V 중의 어느 하나가 노드 B에 메시지를 보낼 수 있음을 알려주면, 노드 U에서 저품질의 서비스 메시지 MU가 없고, 노드 B에서부터 MU의 목적지 출력포트와 노드 V에서 고 품질의 서비스 메시지 MV로 경로가 있고, 노드 B에서 MV의 목표 출력포트로 경로가 있으면, 상기 규칙은 적용될 것이다. 상기 경우에, MV는 노드 B로 전해지고 MU는 컬럼 K+1에서 단계 N+1로 보내질 것이다. 서비스 헤더 비트의 품질은 또한 노드 D 및 E에 도달하는 메시지의 우선 순위를 결정하는 데 사용된다.
본 발명은 실시예의 성능을 향상시키기 위하여 보다 많은 제어 정보와 보다 많은 노드를 사용하는 두 가지 실시예를 포함하고 있다. 이 분야에 있어서 당업자는 상기 기술들을 다른 상호 접속 구조에 적용시킬 수 있음은 명백하다.
상기 설명되고 기술된 상호 접속 구조는 본 발명의 바람직한 실시예이며 첨부된 청구범위에 의해서 결정되는 본 발명의 기술범위에서 벗어나지 않으면서 노드 구조 및 상호 접속 구조에 있어서 다양한 수정과 변형이 가능함은 당연한 것이다.

Claims (15)

  1. 별개의 노드 A 및 E를 포함하여, 다수의 상호 접속된 노드를 포함하는 상호접속 구조로서,
    상기 노드 A는 다수의 데이터 입력 포트, 다수의 데이터 출력 포트 및 다수의 제어신호 입력 포트를 가지며,
    상기 노드 E는 다수의 데이터 입력 포트, 다수의 데이터 출력 포트 및 다수의 제어신호 입력 포트를 가지며,
    노드에 관련된 경로지정 로직으로서, 상호 접속된 노드간에 선택적으로 데이터를 경로지정하기 위한 경로지정 로직을 포함하고,
    상기 노드 A 및 E는 상호 접속 구조에 위치되어 노드 A는 데이터를 노드 E에 경로지정할 수 없고, 노드 E는 노드 A에 데이터를 경로지정할 수 없으며, 어떤 노드도 상호 접속 구조에서 상기 노드 A와 상기 노드 E 양쪽에서부터 경로지정되는 데이터를 가지지 않도록 하며;
    상기 경로지정 로직의 일부로서 포함되고 노드 A와 관련되며 노드 A를 통하여 데이터를 경로지정하기 위해서 노드 E를 통한 데이터의 경로지정에 관한 정보를 이용하는 로직을 포함하는 것을 특징으로 하는 상호 접속 구조.
  2. 제 1 항에 있어서,
    다수의 상호 접속된 노드는 노드 A 및 E와 별개의 노드 F를 포함하며, 상기노드 F는 다수의 데이터 입력포트, 다수의 데이터 출력포트 및 제어신호 출력포트를 가지며,
    상기 노드 A 및 F는 상호 접속 노드 구조에 위치하여 노드 A는 노드 F에 데이터를 경로지정할 수 없고, 노드 F는 노드 A를 통해서 데이터를 경로지정할 수 없으며, 노드 A 및 노드 F로부터 데이터를 경로지정하는 어떤 노드도 상호 접속 구조에 존재하지 않으며,
    노드 A에 관련된 상기 로직은 노드 A를 통하여 데이터를 경로지정하기 위하여 노드 F를 통한 데이터의 경로지정에 관한 정보를 이용하는 것을 특징으로 하는 상호 접속 구조.
  3. 제 2 항에 있어서,
    다수의 상호 접속된 노드는 노드 A, E 및 F와 별개인 노드 B를 포함하며, 상기 노드 B는 다수의 데이터 입력포트, 다수의 데이터 출력포트 및 제어신호 출력포트를 가지며,
    노드 B와 관련된 로직은 제어신호 z를 노드 A에 보낼 수 있는 경로지정 로직의 일부로서 포함되고, 상기 제어신호 z는 노드 B, F 및 E를 거치는 경로지정 가능성에 대한 정보를 포함하며, 노드 A를 거치는 데이터의 경로지정을 위한 노드 A에 관련되는 상기 로직은 노드 B, F 및 E를 거치는 데이터의 경로지정에 대한 정보에 적어도 부분적으로 의존하는 것을 특징으로 하는 상호 접속 구조.
  4. 제 3 항에 있어서,
    다수의 상호 접속된 노드는 노드 A, B, E 및 F와 별개인 노드 C를 포함하며, 상기 노드 C는 다수의 데이터 입력 포트 및 다수의 데이터 출력 포트를 가지며,
    상기 노드 B는 상기 노드 C로 메시지를 보내며,
    상기 노드 E는 상기 노드 B로 제어신호 y를 보내며,
    상기 노드 F는 상기 노드 B로 제어신호 x를 보내며,
    상기 노드 B와 관련된 로직은 제어신호 x, y에 근거하여 노드 A로 비-차단 신호 z를 보내며,
    노드 A는 노드 C로 메시지를 보내며,
    노드 C는 모든 입력 포트로 메시지를 동시에 받아들이는 것을 특징으로 하는 상호 접속 구조.
  5. 노드 A와 B가 노드 C에 데이터를 보내기 위하여 위치되는, 별개의 상기 노드 A, B 및 C를 포함하는 다수의 노드,
    상호 접속 구조의 노드를 선택적으로 결합하는 다수의 상호 접속선,
    노드 B로부터 노드 A로 제어신호를 전송하기 위하여 노드 B에 연결된 선 CBA를 노드 A에 전송하는 제어신호,
    노드 C에 데이터를 전송할 수 있고 노드 A가 노드 C에 메시지를 보내도록 허용되었음을 노드 A에 알릴 수 있는 제어신호 z를 노드 A에 보낼 수 있는 노드 B에 관련된 경로지정 로직.
  6. 제 5 항에 있어서,
    노드 C는 다수의 N 입력 포트를 가지며,
    노드 A 및 B로부터 나온 데이터는 노드 C에 동시에 도달하여 노드 C의 모든 N 입력포트는 동시에 메시지를 받는 것을 특징으로 하는 상호 접속 구조.
  7. 제 6 항에 있어서,
    다수의 노드는 별개의 노드 A, B, C, D, E, F 및 H를 포함하고, 상기 노드 C는 노드 A로부터 노드 D로 데이터를 보내며, 노드 B로부터 노드 H로 데이터를 동시에 보낼 수 있는 것을 특징으로 하는 상호 접속 구조.
  8. 제 7 항에 있어서,
    상기 상호 접속 구조는 계층적이며,
    상기 노드 A는 계층 단계 상에 있으며,
    상기 노드 B, C 및 D는 노드 A의 단계 바로 아래의 계층 단계 상에 있으며,
    노드 E, F 및 H는 상기 노드 B의 단계 바로 아래의 계층 단계 상에 있는 것을 특징으로 하는 상호 접속 구조.
  9. 별개의 노드 A, B 및 C를 포함하는 다수의 노드와 상기 노드를 선택적으로 결합하는 상호 접속선의 집합을 포함하고,
    상기 노드 C는 다수의 메시지 입력포트를 가지며, 상기 노드 A 및 C는 A가 데이터 패킷을 C에 경로지정하도록 구조 내에 위치하며,
    상기 노드 B와 C는 B가 데이터 패킷을 C에 보내도록 구조 내에 위치되며,
    상기 노드 A와 B는 B가 제어신호를 A에 보내도록 네트워크 내에 위치되며,
    메시지를 경로지정하기 위하여 노드 A에서 제어신호 B를 시용하는 로직을 포함하며,
    상기 노드 B는 메시지 MB를 C에 경로지정하며,
    상기 노드 A는 MG와 동시에 도달하는 C에 메시지 MA를 경로지정하며,
    C의 모든 입력포트는 메시지를 동시에 받아들이는 것을 특징으로 하는 상호 접속 구조.
  10. 입력 포트 IA및 IB와 출력포트 OH및 OD를 가지는 노드 C를 포함하는 다수의 상호 접속된 노드,
    입력포트 IB로부터는 접근(access) 가능하지만, 출력포트 OH로부터는 접근이 불가능한 다수의 상호 접속 구조 출력포트, 및
    메시지 MA가 입력 포트 IA에 도달하고 동시에 메시지 MB가 입력포트 IB에 도달할 때, 메시지 MA에 대한 목표 목적지로 출력포트 OD를 거쳐서 경로가 있고 메시지 MB에 대한 목표 목적지로 출력포트 OH를 거쳐서 경로가 있는 것을 확인시키기위해서 상호 접속 구조 내에 포함된 경로지정 로직을 포함하는 것을 특징으로 하는 상호 접속 구조.
  11. 제 10 항에 있어서,
    상기 경로지정 로직은 메시지 MB가 출력포트 OH를 사용하는 것이 봉쇄되지 않고 메시지 MA가 출력포트 OD를 사용하는 것이 차단되지 않도록 된 것을 특징으로 하는 상호 접속 구조.
  12. 제 11 항에 있어서,
    메시지 MA와 메시지 MB의 경로지정을 위한 상기 경로지정 로직은 QOS 기준에 의존하는 것을 특징으로 하는 상호 접속 구조.
  13. 노드 A, B, C, D 및 H 각각은 다수의 입력포트 및 다수의 출력포트를 가지며, 노드 C는 A와 B로부터 메시지를 받고 D와 H로 메시지를 경로지정 하도록 위치되어 있는, 노드 A, B, C, D 및 H를 포함하는 다수의 상호 접속 노드,
    출력 포트 P를 포함하여 P가 노드 C로부터 접근(access) 가능하고 노드 H로부터는 접근 불가능하도록 된 다수의 상호 접속 구조 출력포트, 및
    노드 A가 노드 C로 메시지 MA를 보내고 동시에 노드 B가 노드 C로 메시지 MB를 보낼 때, 노드 C는 노드 D를 거쳐서 MA에 대한 목적지 상호 접속 구조 출력포트로 MA를 경로지정하고 노드 C는 노드 H를 거쳐서 MB에 대한 목적지 상호 접속 구조 출력포트로 MB를 경로지정 하는 것을 확인하도록 상호 접속 구조 내에 포함된 경로지정 로직을 포함하는 것을 특징으로 하는 상호 접속 구조.
  14. 제 13 항에 있어서,
    상기 경로지정 로직은 메시지 MB가 노드 H로부터 차단되지 않고 메시지 MA가 노드 D로부터 차단되지 않음을 확인하는 것을 특징으로 하는 상호 접속 구조.
  15. 제 14 항에 있어서,
    상기 경로지정 로직은 QOS 기준에 응답하는 것을 특징으로 하는 상호 접속 구조.
KR1020027007842A 2000-10-19 2001-10-17 복수개의 제어선을 이용한 복수 단계 최소 로직네트워크상의 처리능력을 증가시키는 확장성 장치 및 방법 Ceased KR20030009334A (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US09/692,073 2000-10-19
US09/692,073 US7221677B1 (en) 2000-10-19 2000-10-19 Scalable apparatus and method for increasing throughput in multiple level minimum logic networks using a plurality of control lines

Publications (1)

Publication Number Publication Date
KR20030009334A true KR20030009334A (ko) 2003-01-29

Family

ID=24779136

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020027007842A Ceased KR20030009334A (ko) 2000-10-19 2001-10-17 복수개의 제어선을 이용한 복수 단계 최소 로직네트워크상의 처리능력을 증가시키는 확장성 장치 및 방법

Country Status (9)

Country Link
US (1) US7221677B1 (ko)
EP (1) EP1261881A4 (ko)
JP (1) JP3950048B2 (ko)
KR (1) KR20030009334A (ko)
CN (1) CN1179214C (ko)
AU (1) AU2002224391A1 (ko)
HK (1) HK1054267B (ko)
IL (1) IL150282A (ko)
WO (1) WO2002033429A1 (ko)

Families Citing this family (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20060171386A1 (en) * 2004-09-01 2006-08-03 Interactic Holdings, Llc Means and apparatus for a scaleable congestion free switching system with intelligent control III
US8065433B2 (en) * 2009-01-09 2011-11-22 Microsoft Corporation Hybrid butterfly cube architecture for modular data centers
US8509078B2 (en) * 2009-02-12 2013-08-13 Microsoft Corporation Bufferless routing in on-chip interconnection networks
US20110202682A1 (en) * 2010-02-12 2011-08-18 Microsoft Corporation Network structure for data center unit interconnection
JP6036690B2 (ja) * 2011-07-07 2016-11-30 日本電気株式会社 分散実行システム及び分散プログラム実行方法
EP3014821A4 (en) 2013-06-28 2017-02-22 Intel Corporation Mechanism to control resource utilization with adaptive routing
US9678800B2 (en) * 2014-01-30 2017-06-13 International Business Machines Corporation Optimum design method for configuration of servers in a data center environment
CN112434483B (zh) * 2020-12-18 2024-07-16 深圳国微芯科技有限公司 数据传输系统的生成方法和数据传输系统
CN113219298B (zh) * 2021-03-24 2022-10-11 昆明理工大学 一种复杂交流电网故障电流行波数值仿真方法

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4814980A (en) * 1986-04-01 1989-03-21 California Institute Of Technology Concurrent hypercube system with improved message passing
US5175733A (en) * 1990-12-27 1992-12-29 Intel Corporation Adaptive message routing for multi-dimensional networks
US5416769A (en) * 1993-07-13 1995-05-16 At&T Corp. Controlled-feedback packet switching system
US5617413A (en) * 1993-08-18 1997-04-01 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration Scalable wrap-around shuffle exchange network with deflection routing
US5996020A (en) * 1995-07-21 1999-11-30 National Security Agency Multiple level minimum logic network
WO1997011543A1 (en) * 1995-09-22 1997-03-27 Mci Communications Corporation Communication system and method providing optimal restoration of failed paths
DE69738175T2 (de) * 1996-08-27 2008-01-31 Nippon Telegraph And Telephone Corp. Verbindungsübertragungsnetzwerk
US6289021B1 (en) 1997-01-24 2001-09-11 Interactic Holdings, Llc Scaleable low-latency switch for usage in an interconnect structure
US5940389A (en) * 1997-05-12 1999-08-17 Computer And Communication Research Laboratories Enhanced partially self-routing algorithm for controller Benes networks
US6285679B1 (en) * 1997-08-22 2001-09-04 Avici Systems, Inc. Methods and apparatus for event-driven routing
US6396814B1 (en) * 1997-09-12 2002-05-28 Kabushiki Kaisha Toshiba Network construction method and communication system for communicating between different groups via representative device of each group
US6754207B1 (en) * 1998-01-20 2004-06-22 Interactic Holdings, Llc Multiple-path wormhole interconnect
US6947433B2 (en) * 2000-09-21 2005-09-20 Avici Systems, Inc. System and method for implementing source based and egress based virtual networks in an interconnection network

Also Published As

Publication number Publication date
EP1261881A1 (en) 2002-12-04
EP1261881A4 (en) 2005-07-27
IL150282A0 (en) 2002-12-01
AU2002224391A1 (en) 2002-04-29
HK1054267B (zh) 2005-08-26
JP2004511992A (ja) 2004-04-15
WO2002033429A1 (en) 2002-04-25
JP3950048B2 (ja) 2007-07-25
HK1054267A1 (en) 2003-11-21
IL150282A (en) 2007-02-11
CN1401081A (zh) 2003-03-05
US7221677B1 (en) 2007-05-22
CN1179214C (zh) 2004-12-08

Similar Documents

Publication Publication Date Title
US5175733A (en) Adaptive message routing for multi-dimensional networks
AU622815B2 (en) Adaptive routing in a parallel computing system
US6754207B1 (en) Multiple-path wormhole interconnect
JPH077507A (ja) 非同期スイッチングノ−ドとそこで使用されるスイッチング素子用論理手段
KR20070007769A (ko) 에러 정정을 이용하는 높은 병렬 스위칭 시스템
US7016363B1 (en) Scaleable interconnect structure utilizing quality-of-service handling
US7130301B2 (en) Self-route expandable multi-memory packet switch with distributed scheduling means
KR20030009334A (ko) 복수개의 제어선을 이용한 복수 단계 최소 로직네트워크상의 처리능력을 증가시키는 확장성 장치 및 방법
US10630607B2 (en) Parallel data switch
KR0170493B1 (ko) 다중 프로세서 시스템을 위한 논블록킹 결함허용 감마 연결망
CA2426377C (en) Scaleable multiple-path wormhole interconnect
US7130302B2 (en) Self-route expandable multi-memory packet switch
US20150023367A1 (en) Parallel data switch
KR0164966B1 (ko) 접힌 구조와 루프백 기능을 갖는 다단계 상호연결망
SU1499367A1 (ru) Устройство маршрутизации
JPH10301910A (ja) データ転送装置
Sabry et al. A New Dynamic Routing Algorithm for Networks-on-Chips
CN119046224A (zh) 一种基于片上网络的多芯片互连的路由系统
Shepherd et al. Next Generation Transputers and Beyond-1: Transputers and Routers: Components for Concurrent Machines
EP1146751A1 (en) Modular hierarchical data switch
EP0598030A1 (en) Scalable self-routing nonblocking message switching and routing network
WO1993003581A1 (en) Message structure for scalable self-routing non-blocking message switching and routing system

Legal Events

Date Code Title Description
PA0105 International application

Patent event date: 20020619

Patent event code: PA01051R01D

Comment text: International Patent Application

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20051220

Comment text: Request for Examination of Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20061110

Patent event code: PE09021S01D

E601 Decision to refuse application
PE0601 Decision on rejection of patent

Patent event date: 20070216

Comment text: Decision to Refuse Application

Patent event code: PE06012S01D

Patent event date: 20061110

Comment text: Notification of reason for refusal

Patent event code: PE06011S01I