armenbadal: CAM սարքեր և նրանց տեստավորումը

1. Բովանդակությամբ հասցեավորվող հիշող սարք

Բովանդակությամբ հասցեավորվող հիշող սարքերը [hgsvz] (Content Addressable Memory – CAM) դրանք հիշող սարքերի մի հատուկ տեսակ են, որոնք օգտագործվում են որոնման մեծ արագություն պահանջող ապարատային կիրառություններում: CAM հիշասարքի բջիջը կարող է լինել բինար՝ 0 և 1 արժեքներ պարունակող, կամ տերնար՝ 0, 1 և x արժեքները պարունակող, որտեղ x-ով նշվում է "դիմակով" փակված և որոնման գործողությանը չմասնակցող արժեքը:

Տիպիկ բինար CAM բջիջը բաղկացած է SRAM բջջից և համեմատող սխեմայից, իսկ տերնար CAM բջիջը բաղկացած է երկու SRAM բջիջներից և համեմատող սխեմայից (նկ. 1): Տերնար CAM բջջի դեպքում SRAM բջիջներից մեկը նախատեսված է ինֆորմացիայի պահպանման համար, իսկ մյուսը՝ պարունակության դիմակավորման համար:

Նկ. 1. SRAM, BCAM բջիջներ [pagiamtzis-jssc:2006]:

Ընդհանուր դեպքում CAM հիշողություններն ունեն բառին կողմնորոշված կառուցվածք (նկ. 2) և հիշողության մատրիցի ամեն մի բառին համապատասխանեցված է վավերականության բիթ: Հիշասարքերի որոշ տիպեր վավերականության բիթ են պահում նաև բառի առանձին կեսերի և քառորդների համար: Այդ տիպի հիշասարքերը հնարավորություն են տալիս որոնում կատարել կես կամ քառորդ ենթաբառերով:

Նկ: 2: CAM հիշողության կառուցվածքը [pagiamtzis-jssc:2006]:

CAM հիշողությունների համար տարրական են գրելու, կարդալու և համեմատման գործողությունները: Գրելու և կարդալու գործողությունները նման են SRAM հիշողություների համանուն գործողություններին, այն բացառությամբ միայն, որ գրելու գործողությունը նաև 1 է վերագրում համապատասխան բառային միավորի վավերականության բիթին: Համեմատման գործողությունը հիշողության մեջ որոնում է տրված բառը: Այս գործողությունն ազդանշանում է hit այն դեպքում, երբ որոնման ընթացքում հանդիպել է տրված բառը և այդ բառի վավերականության բիթը հավասար է եղել 1, և ազդանշանում է miss հակառակ դեպքում:

Քանի որ CAM հիշասարքի բջիջը պարունակում է SRAM բջիջ (կամ բջիջներ) և համեմատող սխեմա, ապա նրան հատուկ են SRAM բջիջների անսարքությունները, ինչպես նաև դրանց են միանում համեմատման սխեմայի անսարքությունները:

CAM հիշասարքերի տեստավորման համար օգտագործվում է մարշ ալգորիթմների ընդլայնված դաս։ Մարշ ալգորիթմը դա վերջավոր թվով մարշ գործողությունների բազմություն է, որտեղ ամեն մի մարշ գործողությունը բաղկացած է հասցեավորման ուղղությունից և վերջավոր թվով մարշ գործողություններից։ Մարշ գործողությունների տիպիկ բազմություն կարող է հանդիսանալ R(D), W(D), WC(D), WCM(D), MISS(D), HIT(D), HITM(D,I), INV, UNL բազմությունը։

Նկատի ունենալով, որ CAM բջիջը բաղկացած է SRAM բջջից և համեմատող սխեմայից, պետք է նշել որ CAM բջջին հատուկ են բոլոր այն անսարքությունները, որոնք հանդիպում են SRAM բջիջներում [Harut2006]: Ի հավելումն նշվածների, ի հայտ են գալիս նաև անսարքություներ, որոնք կապված են համեմատող սխեմայի հետ: [hgsvz] հոդվածում թվարկված են CAM սարքերում հանդիպող և համեմատման գործողության հետ կապված մի քանի անսարքություններ:

2. Առաջադրանքի նկարագրություն

Խնդիր է դրված կառուցել համակարգչային ծրագիր և նրանում իրականացնել հետևյալ բաղադրիչները.

բովանդակությամբ հասցեավորվող հիշող սարքի մոդել,
բջջի անսարքության մոդել,
մարշ ալգորիթմի մոդել:

Ինչպես նաև.

Ապահովել հիշող սարքում անսարքությունների ներմուծման մեխանիզմ:
Ապահովել մարշ ալգորիթմների գործարկումը հիշողության զանգվածի վրա:
Ալգորիթմի գործարկումից հետո կուտակված տվյալներն արտածել հարմար տեսքով՝ հետագա վերլուծությունների համար:

3. Ծրագրի ընդհանուր նկարագրություն

Ստեղծված համակարգչային ծրագիրը հնարավորություն է տալիս պրիմիտիվ կառուցվածքների միջոցով նկարագրել հիշողության զանգվածը, հիշողության բջջի անսարքությունները, հիշողության մոդելի վրա գործարկվող խնդիրները: Օգտագործողի պահանջները ծրագիրն են ներկայացվում տեքստային ֆայլի տեսքով: Աշխատանքի արդյունքները նույնպես արտածվում են տեքստային ֆայլում:

Հիշող սարքի սահմանում

Հիշող սարքի մոդելը սահմանվում է Memory կառուցվածքի միջոցով, որի երեք դաշտերը՝ NumberOfBits, NumberOfWords և Macro, համապատասխանաբար ցույց են տալիս բիթերի քանակը հիշող սարքի մեկ բառում, բառերի քանակը հիշող սարքի զանգվածում և CAM հիշասարքի աշխատանքային ռեժիմը:

Ահա մի օրինակ, որտեղ սահմանված է 16 բառ ունեցող և Single ռեժիմում աշխատող CAM հիշող սարք, որի ամեն մի բառն ունի 8 բիթ.

Memory
{
    NumberOfBits = 8
    NumberOfWords = 16
    Macro = "Single"
}

Անսարքության սահմանում

Հիշող սարքի մեկ բջջի վրա անսարքության նկարագրման համար օգտագործվում է Fault կառուցվածքը՝ իր Row – հիշողության զանգվածի տողը (CAM հիշողության բառը), Column – հիշողության զանգվածի սյունը (CAM բառի բիթը՝ 0-ից սկսվող ձախից-աջ համարակալմամբ) և Type դաշտերով:

Ստորև բերված օրինակը հիշողության զանգվածի երրորդ տողի երկրորդ բջջում ներմուծում է "F-0" անսարքությունը.

Fault
{
    Row = 3
    Column = 2
    Type = "F-0"
}

Fault կառուցվածքի Type դաշտի արժեքն ամբողջովին պայմանական է և կախված է անսարքությունների իրականացումից։ Համակարգչային ծրագրի այս իրականացման մեջ հախատեսված են հետևյալ անսարքությունները [hgsvz]. Always-Match-Fault, Always-Mismatch-Fault, Partial-Match-Fault-0, Partial-Match-Fault-1, Conditional-Match-Fault-0, Conditional-Match-Fault-1, Stuck-Valid-Bit-Fault, Stuck-Invalid-Bit-Fault, Mask-Column-Fault:

Օրինակ, բջջի մեջ Always-Mismatch-Fault անսարքության ներմուծումը նշանակում է, որ համեմատման գործողությունը միշտ տալու է բացասական պատասխան:

Տեստային խնդրի սահմանում

Տեստային խնդիրը նկարագրվում է Task կառուցվածքով, որի դաշտերն են Name – խնդրի անվանումը, Algorithm – մարշ ալգորիթմ, OutputFile – արդյունքների ֆայլ, որտեղ արտածվում են խնդրի կատարման արդյունքները: (Գործիքի ընթացիկ իրականացման մեջ Name դաշտը ոչ մի իմաստ չի կրում։)

Հետևյալը տեստային խնդրի նկարագրման օրինակ է.

Task 
{
    Name = "T0"
    Algorithm = "->(W(SO),R(~{}SO))"
    OutputFile = "../t0.log.txt"
}

Algorithm դաշտի արժեքը տեքստային տեսքով տրված մարշ ալգորիթմ է, որի մասին տես marchops:

Իրականացված մարշ ալգորիթմներ

Մարշ ալգորիթմը դա մարշ տարրերի (էլեմենտների) վերջավոր հաջորդականություն է, իսկ մարշ տարրը մարշ գործողությունների վերջավոր հաջորդականություն է: Բացի մարշ գործողություններից մարշ տարրը պարունակում է նաև հասցեավորման ուղղությունն ու աշխատանքային ռեժիմը: Օրինակ,


=>_H(WH(SO,H0),RH(SO,H0)):

արտահայտությունը ներկայացնում է մարշ տարր, որի հասցեավորման ուղղությունը նշված է =>, աշխատանքային ռեժիմը նշված է H, իսկ գործողությունների ցուցակը պարունակում է WH և RH գործողությունները:

Ստորև թվարկված են համակարգչային ծրագրում իրականացված մարշ գործողությունները:

W(D) - Ընթացիկ բառում գրում է D:
WH(D,H) - Ընթացիկ բառի H կեսում գրում է D տվյալը:
WQ(D,Q) - Ընթացիկ բառի Q քառորդում գրում է D տվյալը:
WM(D,M) - Ընթացիկ բառում գրում է D տվյալը՝ օգտագործելով M դիմակը:
R(D) - Կարդում է ընթացիկ բառի պարունակությունը՝ սպասելով D տվյալը:
RH(D,H) - Կարդում է ընթացիկ բառի H կեսը՝ սպասելով D տվյալը:
RQ(D,Q) - Կարդում է ընթացիկ բառի Q քառորդը՝ սպասելով D տվյալը:
HIT(D,A) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է միայն և միայն A հասցեում:
HITH(D,A,H) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է միայն և միայն A հասցեի H կեսում:
HITQ(D,A,Q) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է միայն և միայն A հասցեի Q քառորդում:
MISS(D) - Որոնում է D տվյալը՝ սպասելով, որ այն հիշող սարքում չի հանդիպում:
MISSH(D) - Որոնում է D տվյալը՝ սպասելով, որ այն չի հանդիպում որևէ բառի որևէ կեսում:
MISSQ(D)- Որոնում է D տվյալը՝ սպասելով, որ այն չի հանդիպում որևէ բառի որևէ քառորդում:
MHIT(D,A) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է մեկից ավելի անգամներ՝ A ամենափոքր հասցեում:
MHITH(D,A,H) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է ավելի քան մեկ անգամ A ամենափոքր հասցեի H կեսում:
MHITQ(D,A,Q) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է ավելի քան մեկ անգամ A ամենափոքր հասցեի Q քառորդում:
UNL(A) - A հասցեով բառը նշում է որպես ոչ ակտիվ (անվավեր):
UNLH(A,H) - A հասցեով բառի H կեսը նշում է որպես ոչ ակտիվ (անվավեր):
UNLQ(A,Q) - A հասցեով բառի Q քառորդը նշում է որպես ոչ ակտիվ (անվավեր):
INV - Հիշող սարքի ամբողջ պարունակությունը նշում է որպես ոչ ակտիվ:

Ծրագրի գործարկման արդյունքներ

Ծրագրի գործարկումից հետո ամեն մի տեստային խնդրի համար նշված արդյունքների ֆայլում արտածվում են տվյալ խնդրի կատարման ժամանակ ձախողված մարշ գործողությունների արդյունքները, ինչպես նաև հիշողության զանգվածի վիճակը՝ խնդրի կատարումից հետո։

Եթե ծրագրի գործարկման ժամանակ նշված չէ արտածվող տվյալների ձևափոխության ֆորմատ (ֆայլի տեսքով), ապա ամեն մի ձախողված գործողության համար արտածվում է մեկ ինֆորմացիոն տող, որտեղ դաշտերն ունեն հետևյալ իմաստները.

IX	Գործողության ինդեքս,
OP	Գործողության պայմանական անուն,
AA	Ստացված հասցե,
EA	Սպասվող հասցե,
HC	Համընկնումների քանակ,
AD	Ստացված տվյալ,
ED	Սպասվող տվյալ,
FB	Չհամընկած բիթեր,
WS	Բառի հատված,

Օրինակ, =>(W(CH)); -_H(MISSH(CH)) ալգորիթմի կատարումից հետո արտածվել են հետևյալ տվյալները.


Fail 0: IX = 0, OP = MISSH, AA = 0, EA = , HC = 16, AD = , ED = 0101, FB = , WS = 0
Fail 1: IX = 0, OP = MISSH, AA = 0, EA = , HC = 16, AD = , ED = 0101, FB = , WS = 0

Հավելված A-ում բերված են արդյունքների ձևափոխության օրինակներ:

4. Ծրագրի բաղադրիչների իրականացում

Այս գլխում նկարագրված են ծրագրի բաղադրիչներն արդեն կառուցվածքային, ծրագրավորման տեսակետից: Քանի որ ամբողջ գործիքի նախագծման ու իրականացման ժամանակ կիրառվել են այսպես կոչված օբյեկտներին կողմնորոշված ծրագրավորման մեթոդները, ապա այս գլխում շարադրանքը կտարվի ըստ դասերի իրականացման և կօգտագործվի համապատասխան տերմինաբանություն:

Հիշողության զանգվածի մոդել

Բովանդակությամբ հասցեավորվող հիշասարքի զանգվածն իրականացված է MemoryArray դասով: Այն որպես տվյալներ պարունակում է հետևյալ անդամները.

NumberOfBits : Integer - բիթերի քանակ,
numberOfWords : Integer - բառերի քանակ,
arrayOfCells : Array[,] Of MemoryCell - բջիջների զանգված,
memoryMacro : {Single, Half, Quarter} - մոդելի աշխատանքային ռեժիմ,
dataMask : Array[] Of Character - բառի դիմակ,
validBit~:~Array[]~Of~Integer - բառերի վավերականության բիթեր: ներկայացված են աբմողջ թվերի հետևյալ կոդավորմանբ. ZZ = 0x00, Q0 = 0x08, Q1 = 0x04, Q2 = 0x02, Q3 = 0x01, H0 = 0x0C, H1 = 0x03, S0 = 0x0F:

Մոդելի հետ աշխատանքն ապահովող ինտերֆեյս են կազմում MemoryArray դասի հետևյալ մեթոդները.

writeSingle(address : Integer, data : String) – address հասցեում գրում է data տվյալը, վավերականության բիթին վերագրելով S0:
writeHalf(address : Integer, half : Integer, data : String) – data-ն գրանցում է address բառի half կեսում: Համապատասխան վավերականության բիթը դրվում է H0 կամ H1:
writeQuarter(address : Integer, half : Integer, data : String) – data-ն գրանցում է address բառի quarter քառորդում: Համապատասխան վավերականության բիթը դրվում է Q0, Q1, Q2 կամ Q3:
readSingle(address : Integer) : String – վերադարձնում է address հասցեով բառի պարունակությունը:
readHalf(address : Integer, half : Integer) : String – վերադարձնում է address հասցեով բառի half կեսի պարունակությունը:
readHalf(address : Integer, quarter : Integer) : String – վերադարձնում է address հասցեով բառի quarter քառորդի պարունակությունը:
unload(address : Integer, section : Integer) – address հասցեով բառի section (single, half, quarter) հատվածը նշում է որպես ոչ ակտիվ (վավերականության բիթի արժեքը դարձնում է 0):
invalidate() – հիշողության մատրիցի բոլոր բառերի վավերականության բիթերին վերագրում է 0 (ZZ) արժեքը:
compareSingle(data : String) : CompareResult – հիշողության մատրիցում որոնում է data՝ որոնման ժամանակ դիտարկելով միայն S0 արժեքով վավերականության բիթ ունեցող բառերը:
compareHalf(data : String) : CompareResult – հիշողության բառերի կեսերում որոնում է data տվյալը՝ դիտարկելով մաին վավերականության բիթում 1 արժեք ունեցող կիսաբառերը:
compareQuarter(data : String) : CompareResult – հիշողության բառերի քառորդներում որոնում է data-ն՝ նորից դիտարկելով վավերական քառորդները:
program(word : Integer, bit : Integer, fault : Object) – word բառի bit բջջի վրա ներմուծում է fault անսարքությունը:

Հիշող սարքի բջջի մոդել

Հիշողության մեկ բջիջը, որ իրականացված է MemoryCell դասով, հանդիսանում է ինֆորմացիայի պահպանման հիմնական տարր, ինչպես նաև բազային դաս՝ անսարքություն պարունակող բջջի մոդելավորման համար:


Type MemoryCell = Object
    data : Character;

    Procedure Write(d : Character);
    Procedure Read() : Character;
    Procedure Compare(d : Character) : Boolean
End;

Վավերականության բիթերի մոդել

Քանի որ այս աշխատանքում դիտարկվում են ամբողջ բառի, կես բառի, և քառորդ բառի ռեժիմներում աշխատող CAM սարքեր, ապա այդ պատճառով վավերականության բիթերն ամեն մի բառի համար չորս հատ են: Ստորև բերված է հիշող սարքի բառի առանձին մասերի կոդավորումը վավերականության բիթերով.

Ամբողջ բառ	`S0`	xxxx
Առաջին կես	`H0`	xx--
Երկրորդ կես	`H1`	--xx
Առաջին քառորդ	`Q0`	x---
Երկրորդ քառորդ	`Q1`	-x--
Երրորդ քառորդ	`Q2`	--x-
Չորրորդ քառորդ	`Q3`	---x

Վավերականության բիթում "x" արժեքը կարող է դրվել միայն MemoryArray օբյեկտի Write գործողության կատարման ժամանակ, իսկ "x" արժեքը "-" արժեքի կարող է վերածվել Unload և Invalidate գործողությունների կատարման ժամանակ:

Վավերականության բիթերի վրա անսարքություն մոդելավորելու համար պարզապես պետք է համապատասխան բիթի վարքն այնպես մոդելավորել, որ այն ցույց տա կամ մշտական "x", կամ մշտական "-":

Անսարքության մոդելներ

Սույն աշխատանքում դիտարկվել են բովանդակությամբ հասցեավորվող հիշող սարքերի այն անսարքությունները, որոնք կապված են հիշող սարքի զանգվածում որոնման գործողության հետ (սարքի բջջում՝ համեմատման գործողության հետ):

Այս աշխատանքում դիտարկված անսարքությունները մոդելավորելու համար ընդլայնվում են հիշող սարքի բջջի և վավերականության բիթերի հասկացությունները՝ նրանցում մոդելավորելով որևէ կոնկրետ անսարքության վարքը: Օրինակ, համեմատման գորշողության ժամանակ միշտ դրական կամ միշտ բացասական պատասխան տվող բջջի մոդելը ստացվում է հետևյալ կերպ.


Type ConditionalMatchFault = Object(MemoryCell)
    state : Boolean;

    Constructor New(st : Boolean);
    Begin
        state := st
    End New;

    Procedure Compare(d : Character) : Boolean;
    Begin
        res := (data = d);
        If state = data Then
            Compare := res
        Else
            Compare := Not res
    End Compare
End;

Համանմնան եղանակով մոդելավորված են նաև մյուս անսարքությունները: Այն դեպքում, երբ հարկավոր է համակարգչային ծրագրում ավելացնել անսարքության նոր տեսակ, օգտակար կլինի C հավելվածում նկարագրված եղանակի դիտարկումը:

Մարշ ալգորիթմի, էլեմենտի և գործողության իրականացում

Մարշ ալգորիթմն իրականացված է MarchAlgorithm դասով: Այն պարունակում է մարշ տարրերի (էլեմենտ) ցուցակ և ինտերֆեյսային մի մեթոդ՝ ալգորիթմում էլեմենտ ավելացնելու համար:


Type MarchAlgorithm = Object
    elements : Array[] Of MarchElement
End;

Մարշ ալգորիթմը հիշողության մոդելի վրա գործարկելու համար է նախատեսված runOn() մեթոդը, որ արգումենտում ստանում է MemoryArray տիպի օբյեկտային հղումը որպես հիշողության մոդել և TaskResult տիպի օբյեկտային հղումը որպես աշխատանքի արդյունքների կոնտեյներ.


Function RunOn(memory : MemoryArray; results : TaskResult) : Boolean

Այս ֆունկցիայի վերադարձրած բուլյան արժեքը ցույց է տալիս մարշ ալգորիթմի աշխատանքի հաջող կամ անհաջող ավարտը:

Մարշ տարրերն իրականացված են MarchElement դասի միջոցով, որն իրենից ներկայացնում է մարշ գործողությունների ցուցակ, ինչպես նաև պարունակում է հասցեավորման ուղղության և աշխատանքի ռեժիմի մասին հայտանիշները:


Type~ MarchElement = Object
    direction : Integer;
    mode : Integer;
    operations : Array[] Of MarchOperation
End;

Մարշ գործողություններն իրականացված են որպես բազային MarchOperation աբստրակտ դասի իրականացումներ:


Type MarchOperation = Abstract Object
    index : Integer;
    parent : MarchElement;
    data : String;
    mask : String;
    address : Integer;
    section : Integer;
End;

MarchOperation աբստրակտ դասում սահմանված է նաև մարշ գործողությունների վարքն իրականացնող RunOn() մեթոդը` հետևյալ հայտարարությամբ.


Function RunOn(memory : MemoryArraya; address : Integer; result : TaskResult) : Boolean

Այս հայտարարության մեջ արգումենտներն ունեն հետևյալ նշանակությունը. memory – հիշողության մոդել, address – մարշ էլեմենտի ընթացիկ հասցե, result – արդյունքների կոնտեյներ:

Մարշ ալգորիթմի վերլուծություն

Տեստային խնդրի սահմանման մեջ մարշ ալգորիթմը տրվում է տեքստի տեսքով որպես Algorithm պարամետրի արժեք: Այն վերլուծելու և ծրագրում օգտագործելու համար է կառուցված AlgorithmParser-ը: AlgorithmParser տիպի օբյեկտն իր մուտքում ստանում է մարշ ալգորիթմի տեքստային ներկայացումը և parse() մեթոդի միջոցով վերադարձնում է MarchAlgorithm տիպի օբյեկտային հղում:

AlgorithmParser-ը "հասկանում" է հետևյալ EBNF քերականությամբ տրված նկարագրությունները.

Algorithm	=	Element { ';' Element }.
Element	=	('->'\|'<-'\|'<->'\|'-') ('S'\|'H'\|'Q')? '(' Operation { ',' Operation } ')'.
Operation	=	'W' '(' Data ')'
	\|	'WH' '(' Data ',' 'Number' ')'
	\|	'WQ' '(' Data ',' 'Number' ')'
	\|	'WM' '(' Data ',' Data ')'
	\|	'R' '(' Data ')'
	\|	'RH' '(' Data ',' 'Number' ')'
	\|	'RQ' '(' Data ',' 'Number' ')'
	\|	'HIT' '(' Data ',' Address ')'
	\|	'HITH' '(' Data ',' Address ',' Half ')'
	\|	'HITQ' '(' Data ',' Address ',' Quarter ')'
	\|	'MISS' '(' Data ')'
	\|	'MISSH' '(' Data ')'
	\|	'MISSQ' '(' Data ')'
	\|	'HIT' '(' Data ',' Address ')'
	\|	'HITMASK' '(' Data ',' Address ',' Data ')'
	\|	'HITH' '(' Data ',' Address ',' 'Number' ')'
	\|	'HITQ' '(' Data ',' Address ',' 'Number' ')'
	\|	'MISS' '(' Data ')'
	\|	'MISSH' '(' Data ')'
	\|	'MISSQ' '(' Data ')'
	\|	'MHIT' '(' Data ',' Address ')'
	\|	'MHITH' '(' Data ',' Address ',' 'Number' ')'
	\|	'MHITQ' '(' Data ',' Address ',' 'Number' ')'
	\|	'UNLOAD'
	\|	'UNLOADH' '(' 'Number' ')'
	\|	'UNLOADQ' '(' 'Number' ')'
	\|	'INVAL'.
Data	=	'SO' \| '~SO' \| 'CH' \| '~CH' \| 'BitPattern'.
Address	=	'AC' \| 'Number'.

Տեստային խնդրի գործարկումը

Հիշողության մոդելի վրա անսարքությունների ներմուծումն ու տեստային ալգորիթմի գործարկումն իրականացնում է TaskRunner դասի Run() պրոցեդուրայով.


Function TaskRunner.Run(project : CamTestProject) : Boolean;
    For Each Task Do
        ա) Ստեղծել հիշողության մոդել,
        բ) Ներմուծել անսարքությունները,
        գ) Գործարկել ալգորիթմները,
        դ) Վերլուծել ստացված արդյունքները
    End
End Run

Օրինակ, եթե 8x8 չափերով հիշող սարքի (0,0) բջջում ներմուծված է Always Mismatch Fault անսարքությունը, ապա


=>(W(SO)); -(MHIT(SO,0))

ալգորիթմի կատարումից հետո ստացվում է հետևյալ արդյունքը.


Fail 0: OP = MHIT, AA = 1, EA = 0, HC = 7,ED = 11111111, FB = x-------

Այս արդյունքները ցույց են տալիս, որ "11111111" տվյալը հիշող սարքում հանդիպել է երկու և ավելի անգամներ, սակայն սպասված 0 ամենափոքր հասցեի փոխարեն ստացվել է 1 ամենափոքր հասցեն:

Ամփոփում

Աշխատանքի կատարմանը նախապատրաստվելիս և կատարման ընթացքում ուսումնասիրվել են բովանդակությամբ հասցեավորվող հիշող սարքերի կառուցվածքը, ինչպես նաև նրանցում հանդիպող և որոնման գործողության հետ կապված անսարքությունների մի քանի տիպեր:

Ստեղծվել է համակարգչային ծրագիր, որը մոդելավորում է հիշող սարքն ու նրա զանգվածում, վավերականության բիթերում և դիմակավորման ռեգիստրում հանդիպող որոշ անսարքություններ:

Մոդելավորված են այն տիպիկ անսարքությունները, որոնք առավել հաճախ են հանդիպում բովանդակությամբ հասցեավորվող հիշող սարքերում: Եվ ապա մոդելավորվել են հատկապես այն տեստային գործողությունները, որոնք հնարավորություն են տալիս կառուցել այնպիսի տեստային ալգորիթմներ, որոնք կարող են հայտնաբերել մոդելավորված անսարքությունները:

Ծրագիրը թույլ է տալիս խիստ սահմանված քերականությամբ ձևակերպել տեստավորման խնդիրներ, որոնք կարող են պարունակել ա) հիշող սարքի մոդելի նկարագրությունը, բ) հիշող սարքի բոդլում ներմուծվելիք անսարքությունները և գ) հիշող սարքի մոդելի վրա գործարկելու համար նախատեսված տեստային ալգորիթմները:

Ամեն մի տեստային խնդրի խնդրի գործարկումից հետո ստեղծվում են ձախողված գործողությունների մասին մանրամասն տեղեկություններ պարունակող ֆալյեր, որոնց վերլուծությունն օգտագործողին պիտի թույլ տա եզրակացություններ անել տեստային ալգորիթմի արդյունավետության մասին:

Քանի որ համակարգչային ծրագրում նախատեսված է նաև արտածվող տվյալների ձևափոխության մեխանիզմ, օգտագործողը հնարավորություն ունի տեստային խնդիրների արդյունքները ստանալ անմիջապես իրեն հարմար տեսքով (այս հատկությունը էապես կնվազեցնի արդյունքների վերլուծության ժամանակը):

Հավելված A: Արդյունքների ձևափոխությունը

Մարշ գործողությունների կատարման ընթացքում կուտակվում են տվյալներ, որոնք նախատեսված են օգտագործողին մատուցել այն դեպքում, եթե տվյալ գործողության կատարումը ձախողվել է: Սակայն դժվար է գուշակել, թե ի՞նչ տեսքով է ուզում օգտագործողն ստանալ այդ տեղեկությունները: Այս խնդիրը լուծելու համար ստեղծվել է ելքային տվյալների ձևափոխման մեխանիզմ, որի միջոցով հնարավոր է արդդյունքները ստանալ եթե ոչ կամայական, ապա գոնե շատ բազմազան տեսքերով:

Ձևափոխության կանոնները տրվում են տեքստային ֆայլի մեջ և ունեն հետևյալ տեսքը.


@PROLOG
... text for prolog ...
@END

@FORMAT
... text which contains placeholders ...
@END

@EPILOG
... text for epilog ...
@END

@PROLOG հատվածում տրվում այն տեքստը, որը պիտի արտածվի ելքային ֆայլի սկզբում: @FORMAT հատվածում տրվում է ամեն մի ձախողված գործողության տեղեկությունների արտածման տեսքը, որտեղ \ref{sec:resus} բաժնում նկարագրված դաշտերի փոխարինվում են "@" սիմվոլով սկսվող նույն անունով: Օրինակ, եթե պետք է ստանալ գործողության անունը, ապա ֆորմատի տեքստում պետք է գրել @OP: @EPILOG հատվածում էլ այն տեքստն է, որ պետք է կցվի ելքային ֆայլի վերջում:

Հավելված B: Նոր մարշ գործողության ավելացում

Եթե ծրագրի ներկա տարբերակում իրականացված գործողությունները չեն բավարարում որևէ կոնկերտ խնրի իրականացման համար, ապա հեշտությամբ կարելի է ծրագրում իրականացնել կամայական նոր մարշ գործողություն:

Նոր գործողություն ավելացնելու համար առաջին հերթին պետք է պատրաստել նրա իրականացում դասը որպես MarchOperation դասի ժառանգ և անպայմանորեն իրականացնել հետևյալ երկու աբստրակտ մեթոդները.


public abstract bool runOn( MemoryArray memory, int address, 
            int section, TaskResult result );
public abstract string Name { get; }

Դիցուք անհրաժեշտ է ավելացնել OpXYZ գործողությունը:


class OpXYZ : MarchOperation 
{
    public OpXYZ(int arg0, string arg1)
    {
        Address = arg0;
        Data = arg1;
    }
    
    public override string Name
    {
        get { return "OpXYZ"; }
    }

    public override bool runOn(MemoryArray memory, int address, 
            int section, TaskResult result)
    {
        /* Behaviour of operation OpXYZ. */
        return true; // or false
    }

    public override string ToString()
    {
        return "OpXYZ(" Convert.ToString(Address) + "," + Data + ")";
    }
}

Այնուհետև AlgorithmParser դասի Token թվարկման մեջ ավելացնել նոր գործողությանը համապատասխան թոքեն, օրինակ, xXYZ: AlgorithmParser դասում ավելացնել մի մեթոդ, որն իրականացնում է նոր ավելացրած գործողությունը նկարագրող տեքստի քերականական վերլուծությունը.


private OpXYZ parseOpXYZ()
{
    /* syntax analysis of operation */
}

Եվ ապա ParseOperation մեթոդում ավելացնել հետևյալ ճյուղը.


// ...
if (lookahead == Token.xXYZ)
    return parseOpXYZ();
// ...

Հավելված C: Նոր անսարքության ավելացում

Ինչպես արդեն նշվեց, բջջի անսարքությունը մոդելավորված է MemoryCell դասի ընդլայնմամբ: Հետևաբար նոր անսարքություններ մոդելավորելու համար բավական է կամ նորից ընդլայնել MemoryCell դասը, կամ ընդլայնել արդեն մոդելավորված անսարքությունները մոդելավորող դասը:


class MemoryCell
{
    protected char data = '0';

    public MemoryCell()
    { /* ... */ }

    public MemoryCell(char ch)
    { /* ... */ }

    public virtual char read()
    { /* ... */ }

    public virtual void write(char ch)
    { /* ... */ }

    public virtual bool Compare(char ch)
    { /* ... */ }
}

Վավերականության բիթերի աշխատանքի հետ կապված անսարքությունները մոդելավորելու համար պետք է ընդլայնել ValidBit դասը: Ստորև բերված է այդ դասի նկարագրությունը.


class ValidBit
{
    protected int bitValue = 0x00;

    public virtual int Value()
    { /* ... */ }

    public ValidBit() { }

    public virtual void Set(int val)
    { /* ... */ }

    public virtual void UnSet(int val)
    { /* ... */ }
}

Այնուհետև, երբ արդեն պատրաստ են անսարքությունները մոդելավորող դասերը, MemoryArray դասի InjectFault մեթոդում պետք է նշել այդ անսարքությունն իդենտիֆիկացնող տեքստը և որոշել, թե որտեղ է տեղադրվելու անսարք բջիջը կամ վավերականության բիթերը (դիմակի ռեգիստր, հիշող սարքի զանգված կամ վավերականության բիթերի զանգված):

Գրականություն

pagiamtzis-jssc:2006, Kostas Pagiamtzis and Ali Sheikholeslami, Content-addressable memory ({CAM}) circuits and architectures: A tutorial and survey, IEEE Journal of Solid-State Circuits, March, 2006
hgsvz, Grigoryan H. and Harutyunyan G. and Shoukourian S. and Vardanian V. and Zorian Y., Generic BIST Architecture for Testing of Content Addressable Memories, 2011
SidorB02, Piotr R. Sidorowicz and Janusz A. Brzozowski, A framework for testing special-purpose memories, IEEE Trans. on CAD of Integrated Circuits and Systems, 21, 12, 2002
Harut2006, Harutunyan, G. and Vardanian, V. A. and Zorian, Y. Zorian, Minimal March Test Algorithm for Detection of Linked Static Faults in Random Access Memories, Proceedings of the 24th IEEE VLSI Test Symposium, VTS '06, 2006, 120-127, IEEE Computer Society,
art0, Y. Zorian, Built-In-Self-Test Technique for Content-Addressable Memories, US Patent 5107501, 1992
art1, W. K. Al-Assadi and A. P. Jayasumana and Y. K. Malaiya, On fault modeling and testing of content-addressable Memories, IEEE International Workshop on Memory Technology, Design and Testing, 1994
art2, J. Zhao and S. Irrinki and M. Puri and F. Lombardi, Testing SRAM-Based Content Addressable Memories, IEEE Transactions on Computers, 2000
art3, Zh. Xuemei and Y. Yizheng and Ch. Chunxu, Tests for Word Oriented Content Addressable Memories, Asian Test Symposium, 2002
art4, J.-F. Li, Testing Ternary Content Addressable Memories With Comparison Faults Using March-Like Tests, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007
art5, M. Lin and Ch. Yunji and S. Menghao and Q. Zichu and Zh. Heng and H. Weiwu, Testing Content Addressable Memories Using Instructions and March-Like Algorithms, IEEE International Conference on Electronics, Circuits and Systems, 2008
art6 P. Manikandan and B. B. Larsen and E. J. Aas and S. M. Reddy, Test of Embedded Content Addressable Memories, IEEE International Symposium on Electronic System Design, 2010

armenbadal

Pages

Saturday, March 16, 2013

CAM սարքեր և նրանց տեստավորումը