SE525183C2 - Förfarande och medel för behandling med pipelining av datapaket - Google Patents

Description

25 30 nämnda datapaket innehåller information. Förfarande omfattar stegen att associera inforrnationshänvisning med nämnda datapaket, varvid nämnda infonnations- hänvisning omfattar information som hänför sig till längden och positionen för infonnationen innefattad i nämnda datapaket, att lagra inforrnationshänvisningen i ett första register som är åtkomligt för ett behandlingsstadium, att behandla nämnda datapaket i nämnda behandlingsstadium, att, om nämnda behandling av nämnda datapaket resulterar i en förändring av längden eller positionen för nämnda information innefattad i nämnda datapaket, ändra nämnda informationshänvisning så att nämnda informationshänvisning återspeglar nämnda förändring, att efter nämnda behandling lagra informationshänvisningen i ett andra register som är åtkomligt för ett ytterligare behandlingsstadium, och att behandla nämnda datapaket i nämnda ytterligare behandlingsstadium.

Problemet är vidare adresserat av ett behandlingsmedel för behandling med logisk rörledning av ett datapaket, och med en integrerad krets och en datorenhet omfattan- de nämnda behandlingsmedel. Behandlingsmedlet omfattar minst två behandlings- stadier omfattande logikenheter och minst två register för att lagra åtminstone en del av nämnda datapaket. Behandlingsmedlet kännetecknas av att ett första register anordnat att lagra inforrnationshänvisning, associerad med nämnda datapaket och omfattande information som hänför sig till längden och positionen för information innefattad i datapaketet, är åtkomlig för en första logikenhet, att den första logik- enheten är anordnad att behandla datapaketet, att den första logikenheten är anordnad att, om en behandling av datapaketet av den första logikenheten resulterar i en förändring av längden eller positionen för infonnationen innefattad i data- paketet, operera på nämnda infonnationshänvisning så att inforrnationshänvisningen återspeglar förändringen, att ett andra register anordnat att lagra informations- hänvisningen är åtkomlig för en andra logikenhet, att den andra logikenheten är anordnad att behandla datapaketet, och att den andra logikenheten är anordnad att, om en behandling av datapaketet av den andra logikenheten resulterar i en förändring av längden eller positionen för informationen innefattad i datapaketet, 10 15 20 25 30 (_11 i) \,1 ...A (ü L! 3 operera på nämnda informationshänvisning, så att informationshänvisningen återspeglar förändringen.

Med förfarandet och behandlingsmedlet enligt uppfinningen åstadkoms att infornia- tionen innefattad i ett datapaket kan opereras på av en rörledningsprocessor på ett sätt så att längden av information innefattad i datapaketet, och/eller positionen för informationen i datapaketet, ändras. Genom att i enlighet med detta ändra värdet på informationshänvisningen efter sådana operationer kommer information alltid att vara tillgänglig rörande längden och positionen för informationen i datapaketet.

I en utföringsfonn av uppfinningen läggs minst en bit till datapaketet före associe- ring av inforrnationshänvisning till datapaketet. I denna aspekt av uppfinningen om- fattar behandlingsmedlet vidare medel för att lägga till bitar. Härigenom åstadkom- mes att informationen som innefattas i datapaketet när datapaketet lämnar behand- lingsmedlet kan uppta fler bitar än antalet bitar som datapaketet som kommer in i behandlingsmedlet omfattar. I denna utföringsforin är den åtminstone ena biten företrädesvis lagd till datapaketet i början av datapaketet såsom ett blindhuvud, och/eller i slutet på datapaketet såsom ett blindslut. Härigenom åstadkommes att förfarandet och behandlingsmedlet görs lämpliga för behandling av datapaket i ett kommunikationssystem i vilket protokollhuvuden och protokollslut läggs till och avlägsnas från ett datapaket under det att datapaketet sänds inom kommunikations- systemet. Medlet för att lägga till bitar kan lämpligen omfatta en buffert och en skiftare. Med fördel kan skiftaren vara en barrel-shifter. Härigenom åstadkoms att antalet bitar som läggs till till ett datapaket är flexibelt. Antalet bitar som läggs till kan till exempel skilja sig åt mellan olika paket, vara statiskt eller varieras från tid till annan enligt önskemålen hos operatören av behandlingsmedlet.

I en aspekt av uppfinningen avlägsnas minst en bit från datapaketet vid det att data- paketet lämnar det sista av behandlingsstadiema. I denna aspekt av uppfinningen omfattar behandlingsmedlet enligt uppfinningen vidare medel för att avlägsna minst 10 15 20 25 30 x Y f» Lit __; C' 3 (JJ 4 en bit från nämnda datapaket. Härigenom uppnås att användningen av bandbredd görs effektiv och att bitar som inte innehåller information kan avlägsnas.

Företrädesvis fastställs före avlägsnandet av bitar huruvida bitar i datapaketet är överflödiga, och om så är fallet avlägsnas nämnda överflödiga bitar. Härigenom åstadkommes att användningen av bandbredd optimeras. Medlet för att avlägsna bitar kan lämpligen omfatta en skiftare och en buffert. Nämnda skiftare kan med fördel vara en barrel-shifter. Barrel-shiftem kan använda informationshänvisningen för att fastställa hur bitama i datapaketet bör skiftas.

Infonnationshänvisningen kan företrädesvis inkluderas i ytterligare infonnation som är associerad med nämnda datapaket. Det åtminstone ena behandlingsstadiet i nämn- da behandlingsmedel kan då omfatta minst ett register för att lagra inforrnationshän- visning. Härigenom åstadkommes att behandling av informationshänvisning kan göras snabb, och att, när datapaketet delas upp i minst två datablock, informations- hänvisningen kan glida bakåt och/eller framåt inom datablocken för att vara till- gänglig endast för behandlingsstadiet som opererar på endera av datablocken.

Kortfattad beskrivning av ritningarna Fig. 1 visar ett exempel på ett datapaket.

Fig. 2 är en schematisk avbildning av en logisk rörledning för databehandling om- fattande två behandlingsstadier.

Fig. 3a-d visar hur ett datapaket opereras på enligt en utföringsform av uppñnning- CH.

Fig. 4a-d visar hur ett datapaket opereras på enligt en annan utföringsform av upp- finningen. 10 15 20 25 30 Fig. 5 visar ett flödesschema som schematiskt avbildar en utforingsform av forfa- randet enligt uppfinningen.

F ig. 6a-d visar en utforingsform av hur informationshänvisning kan glida bakåt inom en uppsättning av datablock i en logisk rörledning for databehandling.

Fig. 7 visar behandlingsmedel enligt en utforingsform av uppfinningen.

Detaljerad beskrivning De flesta datakommunikationssystem består av ett antal noder i vilka data kan be- handlas och mellan vilka noder datapaket sänds med användning av åtskilliga pro- tokoll. En nod kan använda en eller flera protokoll for sändningen av datapaket. När ett datapaket sänds med användning av ett protokoll kan den sändande noden lägga till ett protokollhuvud och/eller ett protokollslut till datapaketet i syfte att lägga till information som är nödvändig for det tillkommande sändandet av datapaketet. På liknande sätt, när en nod tar emot ett datapaket, kan den mottagande noden avlägsna ett protokollhuvud och/eller ett protokollslut från datapaketet i syfte att packa upp datat som innefattas i datapaketet. Ett typiskt datapaket 100 visas i fig. 1 där använ- dardata 110 är inkapslad i ett huvud 120 som lagts till av ett forsta protokoll, ett huvud 130 och ett slut 140 som lagts till av ett andra protokoll och ett huvud 150 som lagts till av ett tredje protokoll. Under det att datapaketet 100 sänds inom kommunikationsnätet kommer noder återkommande att kapsla in datapaketet 100 genom att lägga till huvuden och/eller slut och avkapsla datapaket 100 genom att avlägsna huvuden och/eller slut.

I fig. 2 visas ett exempel på en rörledning 200 for databehandling omfattande två behandlingsstadier 205a och 205b. Uppenbarligen kan en rörledning 200 omfatta mer än två behandlingsstadier 205. Behandlingsstadiema 205a och 205b omfattar logikenheter 210a respektive 210b, i vilka operationen på data utförs. Ett datablock 10 15 20 25 30 215 omfattande ett eller flera datapaket 100, eller delar av datapaket 100, lagras i ett datablocksregister 220a när det kommer in i rörledningen 200. Ytterligare informa- tion 225 associerad med datablocket 215, såsom till exempel information om vilka instruktioner som skall exekveras på datablocket 215 i rörledningen 200 (se den svenska patentansökningen 0100221-1, inlämnad av sökanden och härrned inför- livad genom hänvisning), kan medfölja datablocket 215 och kan lagras i en eller flera tillkommande register 230a. Den tillkommande informationen 225 såväl som datablocken 215 kan opereras på i rörledningen 200 men detta är inte nödvändigt.

När datablocket 215 och tillkommande information 225 har kommit in i rörled- ningen kommer de att behandlas av logikenheten 210a. Vid en första klocktickning kommer datablocket 215 och tillkommande information 225 att lagras i datablocks- registret 220b respektive ett tillkommande register 230b, vilka register är åtkomliga för behandlingsstadiet 205a och behandlingsstadiet 205b. Ett andra datablock (ej visat i figuren) kan då komma in i registret 220a, möjligen åtföljd av associerad tillkommande information som kan komma in i registret 230a. Vid en andra klock- tickning kommer datablocket 215 och tillkommande information 225 att närvara i behandlingsstadiet 205b under det att det andra datablocket kommer att närvara i behandlingsstadiet 205a. Vid en tredje klocktickning kommer datablocket 215 och tillkommande information 225 att lagras i register 220c respektive 23 Oc, under det att det andra datablocket kommer att lagras i datablocksregistret 220b. Ett tredje datablock 215 kan nu komma in i rörledningen för att lagras i datablocksregistret 220a.

Ett register för att lagra data, såsom registren 220 och 230, kan inte lagra mer än ett förutbestämt maximalt antal databitar, och behandlingsstadiet 205 kan inte behandla mer än ett förutbestämt antal databitar i taget. Vid justering av dataflödet genom rör- ledningen 200 måste dessa begränsningar hos registren 220, 230 och behandlings- stadiet 205 beaktas. En ytterligare konsekvens av detta är att i en behandlingsmiljö med logisk rörledning kommer tilläggandet av bitar från data som närvarar i en rör- ledning 200 att orsaka stora problem avseende till exempel interferens med föregå- 10 15 20 25 30 ende och/eller följande datablock 2 1 5. Därför är konstruktion av processorer med logisk rörledning eller ASIC-processorer som skall användas i system i vilka bitar läggs till och/eller avlägsnas av processorema, såsom till exempel datakommunika- tionssystem där huvuden och/eller slut regelbundet läggs till och avlägsnas från datapaket, inte en enkel process. I syfte att tillåta ändring av storleken för datapaket i rörledningen 200 skulle komplex logik för att dynamiskt skifta data i ett stadium av rörledningen 200 krävas, såväl som flexibelt köande av datablock 215.

En lösning på problemet hur det är möjligt att variera antalet bitar i ett datapaket 100 som behandlas i en rörledning 200 är att lägga till blindbitar till datapaketet 100 före det att datapaketet 100 kommer in i rörledningen 200. En eller flera variabler för att registrera datapaketets 100 längd (d.v.s. antalet bitar innefattad i datapaketet 100) och positionen för den första biten i datapaketet 100 kan då associeras med data- paketet 100. Under det att datapaketet 100 opereras på och längden och positionen för information innefattad i datapaketet 100 ändras, skulle denna variabel (dessa variabler) för registrering kunna ändras i enlighet därmed.

I det följande kommer det att antagas att antalet bitar som läggs till ett datapaket 100 är en multipel av åtta, d.v.s. de adderade bitarna kan enkelt ombildas till bytezar.

Emellertid kan vilket antal som helst av bitar läggas till ett datapaket 100.

Fig. 3 visar schematiskt ett mottaget datapaket 100 som är inkapslat enligt en utföringsform av förfarandet enligt uppfinningen. I fig. 3a visas ett mottaget data- paket 100 omfattande n bytezar. I fig. 3b läggs ett blindhuvud omfattande m bytezar till det mottagna datapaketet 100, såväl som ett blindslut 310 omfattande k byte:ar, varvid det mottagna datapaketet 100, blindhuvudet 305 och blindslutet 310 utgör ett övergångspaket 315. Den skuggade färgen hos blindhuvudet 305 och blindslutet 310 indikerar att de bytezar som innefattas av dessa inte representerar någon information, d.v.s. blindhuvudet 305 och blindslutet 310 är tomma. Tillkommande information 225 omfattande information om längden på informationen innefattad i övergångs- 10 15 20 25 30 ( “l F* D (Il C C. 8 paketet 315, såväl som positionen för informationen innefattad i övergångspaketet 315, här nedan kallad informationshänvisning 320, kan då associeras med över- gångspaketet 315. När övergångspaketet 315 först genereras bör informationshän- visningen 320 företrädesvis innehålla information om längden på det mottagna datapaketet 100 såväl som infonnation om positionen för det mottagna datapaketet 100 i övergångspaketet 315. I fig. 3 illustreras sådan infonnationshänvisning 320 med ett längdvärde 325, som indikerar längden på den del av övergångspaketet 315 som innehåller information, och ett förskjutningsvärde 330, som indikerar positio- nen för den första byte:n i övergångspaketet 315 som innehåller information. Längd- värdet 325 och förskjutningsvärdet 315 kan företrädesvis lagras i olika tillkomman- de register 230. I fig. 3b är längdvärdet 325 n, under det att förskjutningsvärdet 330 är m. I andra implementeringar kan sådan informationshänvisning 320 omfatta information som representerar positionen för den första byte:n av information och den sista byte:n av information i övergångspaketet 315, eller information som rep- resenterar längden av information innefattad i övergångspaketet 315 och positionen för den sista byte:n av infonnation.

Fig. 3c visar att övergångspaketet 315 har exekverats på av en eller flera logik- enheter 210 i rörledningen 200. Delar av blindhuvudet 305 och blindslutet 310 i övergångspaketet 315 i fig. 3c används för att representera information, så att stor- leken på data som innefattar information ökas från n byte till l byte, där l$n+m+k.

I exemplet givet i fig. 3c används p byte:ar av blindhuvudet 305 och q byte:ar av blindslutet 310 för infonnation. Detta visas med att det skuggade området av över- gångspaketet 315 är mindre än det skuggade området av övergångspaketet 315 visat i fig. 3b, varvid ett skuggat område representerar tomma byte:ar. Följaktligen är längdvärdet 325 i fig. 3c n+p+q, under det att förskjutningsvärdet 330 är m-p. Ett exempel på en operation som skulle resultera i detta scenario är inkapslingen av ett datapaket 100 av en sändande nod i ett datakommunikationssystem genom att lägga till ett huvud och ett slut omfattande information som är relevant för den efterföl- jande sändningen av datapaketet 100. Ett annat exempel kan vara ett lokalt delsys- 10 15 20 25 30 tem som används för sändande av data till ett annat lokalt delsystem inom samma nod och som inkapslar data enligt ett protokoll för det lokala delsystemet. Ytterli- gare ett exempel är inkapslingen av data enligt ett protokoll för lokal hårdvara, vilket protokoll används för sändande av data mellan hårdvarukomponenter på ett hårdvaruplan (eng: hardware board) eller mellan hårdvaruplan.

I fig. 3b har de byte:ar som fortfarande inte representerar någon information avlägs- nats, vilket givit ett resulterande datapaket 100 omfattande fler byte:ar än det mot- tagna datapaketet 100. Under antagande att ingen operation som har resulterat i ändringar av längden för lagrad information i övergångspaketet 315, förutom för- ändringama indikerade i fig. 3b, har företagits är mängden av byte:ar som skall avlägsnas lika med m-p vid huvudänden av övergångspaketet 315, och k-q vid slutänden av övergångspaketet 315. Alternativt kan alla byte:ar i övergångspaketet 315 som är tomma behållas som delar av det resulterande datapaketet 100. Avlägs- nandet av överflödiga byte:ar hos övergångspaketet 315 kan med fördel utföras efier det att paketet har lämnat rörledningen 200. Alternativt kan avlägsnandet utföras i slutet av rörledningen 200.

Naturligtvis kan, i stället för att använda endast några av bytezarna i blindhuvudet 305 och blindslutet 310, alla byte:ar i blindhuvudet 305 och blindslutet 310 använ- das för representation av information. I detta fall finns inga överflödiga byte:ar att avlägsna och det resulterande datapaketet 100 skulle vara detsamma som övergångs- paketet 315 som förefinns i det sista behandlingsstadiet i rörledningen 200. Ett scenario kan också uppträda där byte:ar från endast ett av blindhuvudet 305 eller blindslutet 310 har använts för att representera infonnation när övergångspaketet 315 lämnar rörledningen 200. I vissa fall kan det hända att ingen av byte:ama i blindhuvudet 305 eller blindslutet 310 används för att representera information.

Förfarandet enligt uppfinningen kan med fördel också användas för en situation där det resulterande datapaketet 100 innehåller mindre information än det mottagna datapaketet 100. Uppenbarligen kan vilken kombination som helst av tilläggande/- 10 15 20 25 š 13 (fl L, 10 avlägsnande av information vid huvud-/slutänden av det mottagna datapaketet 100 utföras med förfarandet enligt uppfinningen.

Avkapslandet av ett mottaget datapaket 100 enligt en utföringsform av uppfinningen visas i fig. 4. Fig. 4a visar ett mottaget datapaket 100 omfattande n byte:ar av information. Fig. 4b motsvarar fig. 3b, där ett blindhuvud 305 som innehåller m byte:ar och ett blindslut 310 omfattande k byte:ar läggs till det mottagna datapaketet 100, vilket resulterar i ett övergångspaket 315. Fig. 4c visar att övergångspaketet har opererats på av minst en av rörledningens 200 logikenheter 210. Viss information innefattad i det mottagna datapaketet 100 är numera inte användbar, och mängden av byte:ar som representerar tom information har ökat i jämförelse med den ursprungligen skapade övergångspaketet 315. I exemplet i fig. 4c har längden av information innefattad i övergångspaketet 315 reducerats med r byte:ar vid övergångspaketets 315 huvudände och s byte:ar vid slutänden. Värdena på längdvärdet 325 och förskjutningsvärdet 330 har i enlighet dänned ändrats till n- r-s respektive m+r. Ett exempel på en operation som skulle resultera i detta scenario är uppackandet av ett datapaket 100 av en mottagande nod i ett kommunikationssystem, där huvud(-en) och/eller slut, som omfattar information som var relevant endast vid föregående stadier av sändandet, avlägsnas.

I fig. 4d har de överflödiga byte:ama i övergångspaketet 315 som lämnar rörledningens 200 sista behandlingsstadium 215 avlägsnats, vilket resulterat i ett resulterande datapaket 100 som omfattar färre byte:ar än det mottagna datapaketet 100.

I en utföringsform av uppfinningen där alla datapaket 100 som behandlats av en rörledning 200 avkapslas istället för att inkapslas, så att storleken på ett mottaget datapaket 100 alltid är större än det motsvarande resulterande datapaketet 100, kan tilläggandet av byte:ar till det mottagna datapaketet 100, visat i fig. 3b och 4b, 10 15 20 25 30 Pr*- 113? zpd ll utelämnas. Emellertid bör informationshänvisningen 320, också visad i fig. 3b och 4b, företrädesvis genereras även i en sådan utföringsform.

Steget som visas i fig. 3b och 4b kan med fördel utföras före det att det mottagna datapaketet 100 kommer in i rörledningen 200, under det att steget visat i fig. 3d och 4d med fördel kan utföras efter det att övergångspaketet 315 har lämnat rörledningen 200.

Antalet bytezar som läggs till ett mottaget datapaket 100 i syfte att bilda ett över- gångspaket 315 kan variera mellan olika tidpunkter. Varje datapaket 100 som skall behandlas av en rörledning 200 kan till exempel associeras med information om hur många bytezar som skall läggas till det mottagna datapaketet 100.

Ett flödesschema som beskriver en utföringsforrn av förfarandet enligt uppfinningen visas schematiskt i fig. 5. I steg 500 kommer ett datapaket 100 som skall behandlas i en rörledning 200 in i rörledningsmottagaren, vilken kan vara belägen till exempel före registren 220a och 230a i fig. 2. I steg 505 skapas ett övergångspaket 315 ge- nom att öka storleken på det mottagna datapaketet 100 genom att lägga tillkomman- de bytezar till det mottagna datapaketet 100, antingen i form av ett blindhuvud 305, ett blindslut 310 eller både och. I steg 510 skapas informationshänvisning 320 och associeras med övergångspaketet 315. F öreträdesvis är denna informationshänvis- ning 320 en del av den tillkommande informationen 225. Informationshänvisningen 320 kan till exempel vara tillhandahållen i form av ett längdvärde 325 och ett för- skjutningsvärde 330, se fig. 3 och 4. Längdvärdet 325 och förskjutningsvärdet 330 kan företrädesvis lagras i separata tillkommande register 230. I steg 515 kommer övergångspaketet 315 och den tillkommande informationen 225 in i rörledningen 200, så att åtminstone en del av övergångspaketet 315 och den tillkommande infor- mationen 325 är tillgänglig för minst en av behandlingsstadiema 205 i rörledningen 200. I steg 520 behandlar minst ett behandlingsstadium av 205 åtminstone en del av övergångspaketet 315. I steg 525 kontrolleras huruvida någon operation som har 10 15 20 25 30 12 utförts på övergångspaketet 315 i steg 525 resulterar i att informationshänvisningen 320 bör ändras. Om så är fallet beträds steg 530, där informationshänvisningen 320 ändras följdriktigt. Sedan beträds steg 535. Om det i steg 525 visar sig att inga änd- ringar i informationshänvisningen 320 är nödvändiga så beträds steg 535 direkt. I steg 535 kontrolleras huruvida någon ytterligare behandling av övergångspaketet 315 kommer att äga rum, d.v.s. om det kommer att finnas några delar av övergångs- paketet 315 närvarande i några av behandlingsstadiema 205 vid nästa klocktickning.

Om så är fallet återgår förfarandet till steg 520 så att för varje klocktickning vid vilken åtminstone en del av övergångspaketet 315 är tillgängligt för behandling av minst en av behandlingsstadiema 205, körs slingan utgjord av stegen 520, 525, 535 och, om så är tillämpligt, steg 530. Om det visar sig i steg 535 att ingen ytterligare behandling av övergångspaketet 315 kommer att äga rum i rörledningen 200 så beträds steg 540, i vilket det kontrolleras huruvida några bytezar bör avlägsnas från övergångspaketet 315. Detta kan företrädesvis utföras genom att kontrollera värdet för informationshänvisningen 320. Om något eller några bytezar bör avlägsnas från övergångspaketet 315 beträds steg 545, i vilket överflödiga bytezar vid huvudänden och/eller slutänden av övergångspaketet 315 avlägsnas enligt värdet hos informa- tionshänvisningen 320. Steg 550 beträds sedan, i vilket datapaketet 100 lämnar rörledningen. Om det i steg 540 visar sig att inga överflödiga bytezar bör avlägsnas beträds steget 550 direkt.

Flödesschemat i fig. 5 kan ändras på många sätt utan att frångå andan hos uppfin- ningen. Till exempel kan steget 540, i vilket det kontrolleras huruvida några bytezar bör avlägsnas från övergångspaketet 315, utelämnas, och steget 545 kan beträdas direkt efter steget 535. Altemativt kan stegen 540 och 545 utelämnas, varvid data- paket 100 som lämnar rörledningen i steget 550 då inkluderar möjliga överflödiga bytezar. Vidare kan steget 525 till exempel implementeras så att programmet som exekveras på övergångspaketet 315 i steg 520 också exekverar ändringar i infor- mationshänvisningen 320 i samband med exekvering av förändringar i övergångs- paketet 315 som resulterar i behovet av att förändra längdvärdet 325 och förskjut- 10 15 20 25 30 13 ningsvärdet 330. Steg 525 kan då utelämnas. Altemativt kan en flagga sättas i steg 520, vilken indikerar huruvida längden och positionen för informationen innefattad i övergångspaketet 315 har ändrats, och steg 525 skulle då innefatta att kontrollera värdet för nämnda flagga. Såsom diskuterats ovan i samband med fig. 3 och 4 kan steget 505 med fördel utelämnas i uppfinningens utföringsfonner i vilka alla mot- tagna datapaket 100 kommer att avkapslas av rörledningen 200.

Beroende på storleken hos ett mottaget datapaket 100 och bandbredden för rörled- ningen 200 kan ett mottaget datapaket 100 behöva delas upp i två eller flera data- block 215. Storleken på ett datablock 215 är en fråga om implementering och vilken storlek som helst på datablock 215 kan användas. I en utföringsfonn av tillämpning- en, tillhandahållen i exemplifierande syfte, är storleken på ett datablock 215 64 byte:ar. Ett mottaget datapaket 100 innehållande 150 byte:ar av infonnation skulle i denna utföringsfonn delas i minst tre block om 64 byte:ar vardera, utgörande ett övergångspaket 315. I fallet att 150 byte:ar delas upp i tre datablock om 64 byte:ar vardera, innehåller övergångspaketet 315 192 byte:ar, av vilka 42 byte:ar kan distri- bueras mellan ett blindhuvud 305 och/eller ett blindslut 310. Om fler extra byte:ar önskas kan tillkommande tomma block valfritt läggas till övergångspaketet 315, vilket ger ett stort blindhuvud 305 och/eller blindslut 310. Alternativt kan tillkom- mande byte:ar läggas till mottagna datapaket 100 i syfte att bilda ett övergångspaket 315, före det att övergångspaketet 315 delas upp i datablock 215.

När övergångspaketet 315 delas upp i datablock 215 och varje datablock 215 ope- reras på av behandlingsstadiema 205 hos rörledningen 200, bör endast en informa- tionshänvisning 320 företrädesvis associeras med gruppen av datablock 215 som representerar övergångspaketet 315. När ett övergångspaket 315 kommer in i rör- ledningen 200 bör infonnationshänvisningen 320 företrädesvis komma in i rörled- ningen tillsammans med datablocket 215 som kommer in i rörledningen 200 först (jämför tillkommande information 225 som medföljer datablocket 215 i fig. 2).

Under det att andra datablock 215 kommer in i rörledningen 200 kan operationer 10 15 20 25 30 for »ri-f und: iQJ 14 som ger upphov till nödvändigheten att förändra informationshänvisningen 320 utföras på vilket som helst av datablocken 215 hos övergångspaketet 315 närvaran- de i vilket som helst av behandlingsstadiema 205 hos rörledningen 200. Sålunda bör infonnationshänvisningen 320 med fördel vara tillgänglig för logikenheten 210 i behandlingsstadiet 205 i vilket sådana operationer utförs, samtidigt som operatio- nema utförs, i syfte att tillhandahålla möjligheten att hålla informationshänvisningen 320 uppdaterad vid alla tillfällen.

Fig. 6a-d visar flödet för ett övergångspaket 315A genom en rörledning 200 enligt en utföringsfonn av uppfinningen. Övergångspaketet 3 15A delas upp i två data- block 215, betecknade datablock 215 A0 och 215 Al och åtföljda av informations- hänvisningen 320A. Övergångspaketet 3 15A kan omfatta ett blindhuvud 305 och/- eller ett blindslut 310. Tillkommande information 225 förutom informationshänvis- ningen 320 kan medfölja övergångspaketet 315A eller varje individuellt datablock 215 A0-A1, men för att förenkla beskrivningen är denna andra tillkommande infor- mation 225 inte visad i fig. 6.

Rörledningen 200 i fig. 6a-d omfattar tre behandlingssteg 205a-e, var och en omfat- tande en logikenhet 210, kallade logikenhet 2l0a, b respektive c. Det bör förstås att rörledningen 200 kan omfatta vilket antal som helst av behandlingsstadier 205. För en logikenhet 210a-c är en eller flera operationer för att operera på datablocken 215 tillgängliga, vilket visas med att varje logikenhet 210 i fig. 6a-d innehåller en sek- vens 600a-c av ett flödesdiagram. För att förenkla beskrivningen är endast en ope- ration tillgänglig för varje logikenhet 210 i fig. 6, ehuru det bör förstås att mer komplicerade strukturer av operationer kan implementeras.

Med tiden fortskrider varje datablock 215 genom rörledningen 200 så att varje data- block 215 är tillgängligt för behandling i varje logikenhet 210 under ett tidsintervall som motsvarar tiden som fortgår mellan två efterföljande klocktickningar. Varje behandlingsstadium 205 i fig. 6 omfattar ett datablocksregister 220 och ett tillkom- 10 15 20 25 30 var* fâr? s., ..;_ n.) 15 mande register 230. Under den tid då ett visst datablock 215 är tillgängligt for en viss logikenhet 210 kan logikenheten 210 operera på datablocket 215 men detta är inte nödvändigt. Om logikenheten 210 opererar på datablocket 215 bör företrädesvis den tillkommande informationen 225, såsom informationshänvisningen 320, som är associerad med övergångspaketet 315 vilket datablocket 215 är en del av, vara till- gängligt for behandling av logikenheten 215.

Fig. 6a-d illustrerar var och en separata tidsintervall, var och en svarande mot tids- intervallet som passerar mellan två på varandra följande klocktickningar. Fig. 6a illustrerar en forsta klocktickning i vilken det forsta datablocket 215 A0 i över- gångspaketet 3 15A har kommit in i det forsta behandlingsstadiet 205a i rörledningen 200. Informationshänvisningen 320A har också kommit in i behandlingsstadiet 205a och datablocket 215 A0 och inforrnationshänvisningen 320A lagras i ett datablocks- register 220a respektive ett tillkommande register 23 Oa. Såsom visas med den tjocka linjen runt sekvensen 600a opererar logikenheten 205a på datablocket 215 A0 under denna klocktickning. Om längden for informationen innefattad i övergångspaketet 315, eller positionen for nämnda infonnation, påverkas av operationen utford i data- blocket 215 A0 så opererar logikenheten 2l0a på informationsreferensen 320A så att informationsreferensen 320A återspeglar dessa förändringar.

I fig. 6b visas en andra klocktickning i vilken datablocket 215 A0 och informations- hänvisningen 320A har vidarebefordrats till behandlingsstadiet 210b. Datablocket 215 A1 har kommit in i behandlingsstadiet210a. Eftersom datablocket 215 A2 inte åtföljs av någon inforrnationshänvisning 320 vid denna tidpunkt är det tillkomman- de registret 230a tomt (eller innehåller icke användbar information). Logikenheten 210b opererar på datablocket 215 A0, vilket visas med den tjocka linjen runt sek- vensen 600b. Logikenheten 2 10a å sin sida opererar inte på datablocket 215 Al.

Från operationen som utforts på datablocket 215 A0 av logikenheten 210b fastställs huruvida informationshänvisningen 320A bör flyttas framåt till det tillkommande registret 23 0c under nästa klocktickning. Såsom visas med att den "falska" vägen ut 10 15 20 25 30 ïffl* 1.7 »JO 16 ur sekvensen 600b är tjock, fastställs att informationshänvisníngen 320A inte bör flyttas framåt utan i stället bör glida bakåt inom uppsättningen av datablock 215 som utgör övergångspaketet 315. Detta indikerar att under nästa klocktickning kommer datablocket 215 Al att opereras på i stället för datablocket 215 A0.

I enlighet med operationen visad i fig. 6b, visar fig. 6c som illustrerar en tredje klocktickning, en situation där datablocken 215 A0 och 215 A1 var och en flyttas framåt till nästa behandlingsstadium 205c respektive 205b, under det att informa- tionshänvisningen 320A förblir i det tillkommande registret 230b. Datablocket 215 A2 har kommit in i behandlingsstadiet 205a. Under klocktickningen som visas i ñg. 6c opererar logikenheten 2l0b på datablocket 215 Al för att fastställa huruvida informationshänvisningen 320b bör flytta framåt till behandlingsstadiet 205c under nästa klocktickning. Såsom visas i figuren (med att "t":et i sekvensen 600b är tjockt), är operationens resultat att inforrnationshänvisningen 320b bör flyttas framåt till behandlingsstadiet 205c under nästa klocktickning.

I fig. 6d visas en fjärde klocktickning i vilken datablocket 215 AO har lämnat rörled- ningen 200 och datablocket 215 Al och informationshänvisningen 32OA är lagrade i datablocksregistret 220c respektive det tillkommande registret 230c. Såsom indike- ras med den tjocka linjen kring sekvensen 600c utför logikenheten 210c en opera- tion på datablocket 215 A1 under denna klocktickning. Om operationen som utförts på datablocket 215 A1 av logikenheten 210c ändrat längden eller positionen för informationen innefattad i övergångspaketet 315 så förändras informationshänvis- ningen 320A följdriktigt.

Processen att låta infonnationshänvisningen 320 glida bakåt inom uppsättningen av datablock 215 som utgör övergångspaketet 315 är mycket effektiv för att tillhanda- hålla informationshänvisningen 320 till ett behandlingsstadium 205 som är beläget närmare ingången till rörledningen 200 än behandlingsstadiet 205 som sist behand- lade den tillkommande informationen 320. Emellertid kan det i vissa fall vara nöd- 10 15 20 25 30 r. 'fw t .v Qj 41 ...US L f* o: 17 vändigt att låta informationshänvisningen 320 glida framåt inom uppsättningen av datablock 215 så att informationshänvisningen 320 kan opereras på av ett behand- lingsstadium 205 som är längre bort från ingången till rörledningen 200 än behand- lingsstadiet 205 som senast opererade på informationshänvisningen 320. Ett sätt att låta informationshänvisningen 320 glida framåt är att ha synkroniseringsbuffertar vid olika punkter i rörledningen 200. Att låta informationshänvisningen 320 glida framåt kan vara intressant till exempel när övergångspaketet 315 lämnar rörled- ningen 200, i syfte att medge att den första bytezn hos övergångspaketet 315 åtföljs av inforrnationshänvisningen 320. En synkroniseringsbuffert kan då placeras efter det sista behandlingsstadiet 205 i rörledningen 200.

Processen att låta tillkommande information 225 glida bakåt och framåt i uppsätt- ningen av datablock 215 som bildar övergångspaketet 315 är vidare beskrivet i den intemationella patentansökningen PCT/SE01/01133 som är inlämnad av sökanden och härmed införlivad genom hänvisning.

Som ett alternativ till att implementera infonnationshänvisningen 320 som en del av tillkommande information 225 kan inforrnationshänvisningen 320 lagras i ett separat minne som är åtkomligt för alla behandlingsstadier 205.

I fig. 7 visas ett exempel på ett behandlingsmedel 700 anordnat att behandla data- paket enligt förfarandet enligt uppfinningen. Behandlingsmedlet 700 i fig. 7 omfat- tar en mottagare 705, en rörledning 200 och en sändare 710. Ingången på mottaga- ren 705 är förbunden med en inkommande ledning 707 och utgången på mottagaren 705 är förbunden med rörledningen 200. Rörledningen 200 omfattar ett antal be- handlingsstadier 205, jämför fig. 2 och 6, och är vidare förbunden med ingången på sändaren 710, varvid sändaren 710 vidare är förbunden på dess utgångssida med en utgående ledning 712. Den inkommande ledningen 707, rörledningen 200 och den utgående ledningen 712 kan var och en ha olika effektiva bandvidder, d.v.s. hastig- heten med vilken data kan överföras kan skilja sig mellan den inkommande ledning- 10 15 20 25 30 18 en 707, rörledningen 200 och den utgående ledningen 712. Den effektiva bandbred- den hos rörledningen 200 enligt uppfinningen är större än eller lika med de effektiva bandbredderna for den inkommande ledningen 707 och den utgående ledningen 712.

Mottagaren 705 är anordnad att ta emot datapaket 100 som skall behandlas i rörled- ningen 200. Mottagaren 705 omfattar medel 715 för att lägga till bitar till mottagna datapaket 100. Sålunda genereras övergångspaket 3 15 i mottagaren 705. Medlet 715 for att lägga till bitar kan omfatta till exempel en mottagarbuffert 720 i vilken bitar- na i datapaketet 100 lagras vid mottagandet, och en mottagarskiftare 725 till vilken bitarna vidarebefordras från mottagarbufferten 720. Mottagarbufferten 720, som företrädesvis är en FIFO- (engelska: First In First Out) buffert, möjliggör övergång- en mellan den effektiva bandbredden for den inkommande ledningen 707 och den effektiva bandbredden for rörledningen 200. I mottagarskiftaren 725 skiftas bitarna i enlighet med hur många blindbitar som önskas i blindhuvudet 305 och blindslutet 310 i övergångspaketet 315 och det önskade antalet av tillkommande bitar läggs till.

Företrädesvis kan mottagarskiftaren 725 vara en barrel-shifter i vilken skiftningen som utfors av mottagarskiftaren 725 kan varieras. Alternativt kan mottagarskiftaren 725 vara en statisk skiftare.

Sändaren 710 är anordnad att sända resulterande datapaket 100. Företrädesvis om- fattar sändaren 710 medel 7 30 for att avlägsna bitar från övergångspaket 315. Med- let 730 for att avlägsna bitar kan omfatta till exempel en sändarskiftare 735 och en sändarbuffert 740. I sändarskiftaren 725 skiftas bitarna i enlighet med det antal blindbitar som bör avlägsnas i blindhuvudet 305 och blindslutet 310 i övergångs- paketet 315 och överflödiga bitar avlägsnas. Sändarskiftaren 735 kan med fordel vara en barrel-shifter, vilken kan använda informationen hos informationshänvis- ningen 320 som inmatning. Altemativt kan sändarskiftaren 735 vara en statisk skiftare. Sändarbufferten 740, vilken företrädesvis är en F IF O-buffert, möjliggör övergång mellan den effektiva bandbredden hos rörledningen 200 och den effektiva bandbredden hos den utgående ledningen 712. 10 15 20 25 FÜT flfif' Maxi; :LJJ I en utforingsform for behandlingsmedlet enligt uppfinningen som är avsedd att användas i en miljö där den effektiva bandbredden hos rörledningen 200 motsvarar den effektiva bandbredden hos den inkommande ledningen 707 plus flödet av till- kommande bitar tillagda av medlet 715 for att lägga till bitar, kan mottagarbufferten 720 utelämnas från behandlingsmedlet 700. På liknande sätt, om den effektiva band- bredden hos den utgående ledningen 712 motsvarar den effektiva bandbredden hos rörledningen 200 minus flödet av bitar som avlägsnas av medlet 730 for att avlägsna bitar, så kan sändarbufferten 740 utelämnas.

Vid dimensionering av mottagarbufferten 720 bör relationen mellan de effektiva bandbreddema for den inkommande ledningen 7 07 och rörledningen 200 beaktas.

Det förväntade flödet av datapaket 100 på den inkommande ledningen 707 kan också tas i beaktande såväl som den förväntade storleken på datapaketen 100. I en utforingsform av uppfinningen i vilken antalet bitar som läggs till av medlet 715 for att lägga till bitar kan varieras på en datapaketbasis, kan mottagarbufferten 720 möj- liggöra lagring av datapaket 100 som kräver en tillsats av bitar som skulle, om en kontinuerlig ström av datapaket 100 krävde tillsatsen av samma mängd bitar, mot- svara en högre effektiv bandbredd än den effektiva bandbredden for rörledningen 200, under förutsättning att medelantalet for bitar lagda till inkommande datapaket 100 inte bidrar till ett dataflöde som överskrider den effektiva bandbredden for rör- ledningen 200. På liknande sätt bör, vid dimensionering av sändarbufferten 745, relationen mellan den effektiva bandbredden hos rörledningen 200 och den utgående ledningen 712 tas under beaktande.

Behandlingsmedlet 700 kan implementeras som en integrerad krets (d.v.s. som en ASIC), som en del av en integrerad krets, eller som flera integrerade kretsar for- bundna med varandra. 10 20 Föreliggande uppfinning kan med fördel implementeras på vilken nod som helst i ett datakommunikationssystem, i vilket noddatapaket behandlas så att längden eller positionen för information innefattad i datapaketen ändras. Exempel på sådana noder är routrar och telekommunikationsväxlar för paketdata. Ett behandlingsmedel 700 kan då vara en del av en datorenhet, såsom en nätdatorenhet eller en signalbe- handlingsdatorenhet.

Fackmannen inser att den föreliggande uppfinningen inte är begränsad till utförings- formerna som har beskrivits i de medföljande ritningama och den detaljerade be- skrivningen ovan, vilka är presenterade endast i illustrerande syfte, utan den kan i stället implementeras på ett antal olika sätt och den definieras av de följande patent- kraven.

Claims (16)

10 15 20 25 PATENTKRAV

1. Förfarande for behandling med logisk rörledning av ett datapaket (100, 315) i ett behandlingsmedel (700) omfattande minst två behandlingsstadier (205), varvid nämnda datapaket (100) innehåller information, vilket förfarande omfattar steget - att associera (510) informationshänvisning (320; 325, 330) med nämnda datapaket (315), varvid nämnda informationshänvisning (320; 325, 330) omfattar information som hänför sig till längden och positionen fór informationen innefattad i nämnda datapaket (3 15); - varjämte förfarandet är kännetecknat av - att lagra inforrnationshänvisningen (320; 325, 330) i ett forsta register (23 Ob) som är åtkomligt fór ett behandlingsstadium (205a); - att behandla (520) nämnda datapaket (315) i nämnda behandlingsstadium (205a); - att, om nämnda behandling (520) av nämnda datapaket (315) resulterar i en förändring av längden eller positionen fór nämnda information innefattad i nämnda datapaket (315), ändra (530) nämnda informationshänvisning (320; 325, 330) så att nämnda informationshänvisning (320; 325, 330) återspeglar nämnda förändring; - att efter nämnda behandling (520) lagra inforrnationshänvisningen (3 20; 325 , 330) i ett andra register (2300) som är åtkomligt för ett ytterligare behandlingsstadium (205b); - att behandla nämnda datapaket (315) i nämnda ytterligare behandlingsstadium (205b).

2. Förfarande enligt krav 1, vidare omfattande steget att, före steget att associera (510) informationshänvisning (320; 325, 330) med nämnda datapaket (315), lägga till (505) minst en bit (305, 310) till nämnda datapaket (100). 10 15 20 25 ÛÛÛ lin-v ÃQJ 22 .

3. Förfarande enligt krav 2, vari nämnda steg, att lägga till (505) minst en bit (305, 310) till nämnda datapaket (100), omfattar att lägga till ett huvud (305) och/eller ett slut (310) till nämnda datapaket (100). .

4. Förfarande enligt något av föregående krav, vidare omfattande stegen att, vid det att datapaketet lämnar det sista av nämnda minst två behandlingsstadier, be- stämma (540) huruvida bitar i datapaketet (315) är överflödiga, och att, om bitar i datapaketet (315) är överflödiga, avlägsna (545) nämnda överflödiga bitar. .

5. F örfarande enligt något av kraven 1-3, vidare omfattande stegen att, vid det att datapaketet lämnar det sista av nämnda minst två behandlingsstadier, avlägsna minst en bit från datapaketet. .

6. Förfarande enligt något av föregående krav, vari nämnda infonnationshänvisning (320) är inkluderad i ytterligare information (225) som är associerad med nämnda datapaket. .

7. Förfarande enligt något av föregående krav, vari nämnda infonnationshänvisning omfattar ett längdvärde (325) och ett förskjutningsvärde (330), varvid nämnda längdvärde (325) representerar längden hos informationen som är innefattad i nämnda datapaket (315) och nämnda förskjutningsvärde (330) indikerar positionen i nämnda datapaket (315) för informationen som är innefattad i nämnda datapaket (315). .

8. Behandlingsmedel för behandling med logisk rörledning av ett datapaket ( 100, 315), varvid nämnda behandlingsmedel omfattar minst två behandlingsstadier omfattande logikenheter (2l0a, 2l0b) och minst två register (220a, 220b, 220c) för att lagra åtminstone en del av nämnda datapaket (100, 315), kännetecknat aV 10 15 20 25 23 att ett första register (23 Ob) anordnat att lagra inforrnationshänvisning (320), associerad med nämnda datapaket (315) och omfattande information som hänför sig till längden och positionen för information innefattad i datapaketet, är åt- komlig för en första logikenhet (210a), att den första logikenheten är anordnad att behandla datapaketet, att den första logikenheten (210a) är anordnad att, om en behandling av datapaketet av den första logikenheten resulterar i en förändring av längden eller positionen för informationen innefattad i datapaketet, operera på nämnda infonnationshänvisning (320) så att infonnationshänvisningen återspeglar förändringen, att ett andra register (230c) anordnat att lagra informationshänvisningen (320) är åtkomlig för en andra logikenhet (210b), att den andra logikenheten är anordnad att behandla datapaketet, att den andra logikenheten (210a) är anordnad att, om en behandling av datapaketet av den andra logikenheten resulterar i en förändring av längden eller positionen för informationen innefattad i datapaketet, operera på nämnda inforrnationshänvisning (320), så att inforrnationshänvisningen återspeglar förändringen. .

9. Behandlingsmedel enligt krav 8, vidare omfattande medel (715) för att lägga till minst en bit till nämnda datapaket (100).

10. Behandlingsmedel enligt krav 9, vari nämnda medel (715) för att lägga till minst en bit till nämnda datapaket (100) omfattar en buffert (720) och en skiftare (725).

11. ll.Behandlingsmedel enligt något av kraven 8-10, vidare omfattande medel (730) för att avlägsna minst en bit från nämnda datapaket (315). 10 15 24

12. Behandlingsmedel enligt något av kraven 8-11, vari medel (730) for att avlägsna omfattar en skiftare (735) och en buffert (740).

13. Behandlingsmedel enligt krav 10 eller 12, vari nämnda skiftare (725, 735) är en barrel-shifter.

14. Behandlingsmedel (700) enligt något av kraven 8-13, vari nämnda forsta register (230) for att lagra informationshänvisning omfattar ett register (23 0) for att lagra ett längdvärde (325) och ett annat register (230) for att lagra ett förskjutnings- värde (330).

15. Integrerad krets, kännetecknad av ett behandlingsmedel (700) enligt krav 9.

16. En datorenhet, kännetecknad av ett behandlingsmedel enligt krav 9.