Saturday, March 30, 2013

Plain TeX հիմունքներ

Տարիներ առաջ ես սկսեցի հետաքրքրվել գիտական տեքստերի պատրաստման TEX համակարգով։ Սովորելուն զուգահեռ աշխատում էի համակարգված նկարագրել իմ կուտակած գիտելիքները։ Արդյունքում ստացվեց Plain TEX տարբերակի մասին 48 էջանոց մի ուղեցույց, որն էլ ներկայացնում եմ ստորև։ [Նշեմ, որ այս հրապարակումը նկարագրում է Plain TEX համակարգը, այլ ոչ թե LATEX-ը։]

http://issuu.com/armenbadalian/docs/armentexi?mode=window&viewMode=singlePage

Friday, March 29, 2013

Այլ ծրագրի աշխատեցնելը Java ծրագրից

Ինչ որ մի անգամ ինձ պետք էր անել այնպես որ օգտագործողի գրաֆիկական ինտերֆեյսում (GUI) անընդհատ ռեժիմով արտածվեն մեկ այլ պրոցեսում աշխատեցրած ծրագրի արտածման ստանդարտ հոսքի (stdout) և սխալների ստանդարտ հոսքի (stderr) հաղորդագրությունները։ Այս գրառման մեջ ես պարզեցրած օրինակով ցույց կտամ, թե ինչպես դա արեցի։

1. NetBeans աշխատանքային միջավայրում ստեղծենք ScriptRunner անունով պրոյեկտը և նրա լռելությամբ ստեղծված scriptrunner փաթեթում ավելացնենք JFrame դասից ժառանգված MainWindow անունով պատուհանը։

2. Պատուհանի վրա ավելացնենք արտաքին սկրիպտի ճանապարհը նշելու, այն աշխատեցնելու և արդյունքներն արտածելու հետևյալ երեք օբյեկտները։
  • txtScript : JTextField - սկրիպտի կամ հրամանի ճանապարհը նշելու դաշտ,
  • btnRun : JButton - աշխատանքը սկսելու կոճակ,
  • areaResults : JTextArea - արդյունքներն արտածելու տիրույթ:
Դասավորենք օբյեկտներն այնպես, որ նրանք ունենան ստորև բերված նկարի տեսքը։

3. "Run" կոճակի կոնտեքստային մենյուից ընտրենք Events->Action->actionPerformed գործողությունը, որի հետևանքով պատուհանի կոդի հատվածում կստեղծվի btnRunActionPerformed անունով մեթոդի դատարկ մարմինը։ Այս մեթոդը կանչվելու է, երբ սեղմենք "Run" կոճակը։
private void btnRunActionPerformed(java.awt.event.ActionEvent evt) { 
  //
}


Արտաքին ծրագիրն աշխատեցնում եմ Process դասի օգնությամբ, որը հնարավորություն է տալիս իր getInputStream մեթոդից ստեղծել կարդալու հոսք և կարդալ արտաքին ծրագրի արտածման ու սխալների ստանդարտ հոսքերի արտածումները։ Օրինա, եթե պետք է Java ծրագրից աշխատեցնել ls ծրագիրը, ապա պետք է նախ ProcessBuilder դասի կոնստրուկտորին տալ աշխատեցվելիք ծրագրի անունը, ապա կանչելով նրա start մեթոդը, ստեղծել նոր պրոցես։
Process ps = (new ProcessBuilder("ls")).start();
InputStream is = ps.getInputStream();
Պրոցեսի տված հաղորդագրությունները սինխրոն կարդալու համար ստեղծել եմ մի thread, որը կարդում է պրոցեսի արտածման հոսքի հետ կապված ընթերցման հոսքի պարունակությունը և արտածում է areaResults դաշտում։

Ահա btnRunActionPerformed մեթոդի իրականացումը։
private void btnRunActionPerformed(java.awt.event.ActionEvent evt) {                                       
  try {
    // պրոցեսի ստեղծում
    ProcessBuilder pb = new ProcessBuilder(txtScript.getText());
    // սխալների հոսքն ուղղել stdout-ի վրա
    pb.redirectErrorStream(true); 
    // պրոցեսի գործարկում
    Process procFlow = pb.start();
    
    // վերցնել պրոցեսի արտածման հոսքը
    InputStream inp = procFlow.getInputStream();
    final BufferedReader reader = 
            new BufferedReader(new InputStreamReader(inp));

    // thread-ի ստեղծում
    Thread outputThread = new Thread() {
      @Override
      public void run() 
      {
        try {
          // ապահովել reader-ը,
          synchronized(reader) {
            String text = "";
            // քանի դեռ կարդալու բան կա, կարդալ
            while(null != (text = reader.readLine())) {
              // տեքստը կցել areaResults-ի պարունակության պոչից
              areaResults.append(text + "\n");
              // կուրսորը տեղափոխել տեքստի վերջը
              areaResults.setCaretPosition(areaResults.getText().length());
            }
          }
        }
        catch (Exception e) {}
      }
    };
    
    // կարդացող thread-ի գործարկում
    outputThread.start();
  }
  catch(IOException ex) {
    JOptionPane.showMessageDialog(this, ex.getMessage(), 
               "Error", JOptionPane.ERROR_MESSAGE);
  } 
}

* * *
Ծրագիրը փորձարկելու համար ստեղծել եմ Bash-ի մի սխրիպտ, որը երկու վայրկյան ընդմիջումներով հաղորդագրություններ է արտածում արտածման ստանդարտ հոսքի վրա։
#!/bin/bash

for m in 1 2 3 4 5 6 7 8 9 10 11 12
do
  echo Message number: $m
  sleep 2
done
Ծրագիրն աշխատեցնելուց հետո txtScript դաշտում ներմուում եմ սկրիպտի ճանապարհը ու սեղմում եմ Run կոճակը։ Արդյունքն այն է, ինչ ես սպասում էի։


Friday, March 22, 2013

Vector to List, Vector to String

Հանդիպեցի մի խնդրի, որտեղ պետք էր Common Lisp վեկտորից (միչափանի զանգված), որի տարրերը (0..255) միջակայքի ամբողջ թվեր են, ստանալ նրա տարրերի ցուցակը և այդ նույն տարրերի տասնվեցական ներկայացումներից բաղկացած տողը։ Օրինակ, վեկտորը կարող է լինել այսպիսին.
(defparameter vec
    #(12 34 210 127 32 7 25 87 193 41 42 200 63 0 137 161))
(print vec)

#(12 34 210 127 32 7 25 87 193 41 42 200 63 0 137 161)
Դե, առաջին միտքն այն էր, որ loop ցիկլով կարելի է անցնել վեկտորի տարրերով և դրանք հավաքել ցուցակի մեջ.
(defparameter veclis
    (loop for e across vec collect e))
(print veclis)

(12 34 210 127 32 7 25 87 193 41 42 200 63 0 137 161)
Իսկ տասնվեցական նիշերից կազմված տողը ստանալու համար կարելի է format ֆունկցիայով ստանալ թվի տասնվեցական ներկայացումը՝ օգտագործելով "~2,'0x" ֆորմատավորման տողը։ Այդ տասնվեցական տեսքերը հավաքել ցուցակի մեջ, ապա այդ ցուցակի նկատմամբ կիրառել concatenate ֆունկցիան, իհարկե, apply ֆունկցիայի միջոցով։
(defparameter vecstr
    (apply #'concatenate 'string 
           (loop for e across vec 
                 collect (format nil "~2,'0x" e))))
(print vecstr)

"0C22D27F20071957C1292AC83F0089A1"
* * *
Բայց, սրանք շատ տգեղ պրոցեդուրային լուծումներ են։ Common Lisp լեզվի reduce ֆունկցիան արգումենտում ստանում է բինար ֆունկցիա և մի որևէ հաջորդականություն, իսկ վերադաձնում է մի արդյունք, որը ստացվում է հաջորդականության բոլոր տարրերի միջև կիրառելով տրված բինար գործողությունը։ Օրինակ, եթե վեկտորը պարունակում է 1-ից 9 թվերը, ապա դրանց գումարը հաշվելու համար կարելի է գրել.
(reduce #'+ 
        #(1 2 3 4 5 6 7 8 9)
        :initial-value 0)
45
Իսկ նույն այդ վեկտորի թվերի քառակուսիների գումարը հաշվելու համար՝
(reduce #'(lambda (a b) (+ a (* b b))) 
        #(1 2 3 4 5 6 7 8 9)
        :initial-value 0)
285
Հիմա, վեկտորից ցուցակ ստանալու համար օգտագործենք (lambda (x y) (cons y x)) ֆունկցիան և '() սկզբնական արժեքը։ reduce ֆունկցիայի արժեքը ստացվում է շրջված տեսքով, դրա համար էլ լրացուցիչ կիրառվել է reverse ֆունկցիան։
(defparameter veclis
    (reverse (reduce #'(lambda (x y) (cons y x)) vec :initial-value '())))
(print veclis)

(12 34 210 127 32 7 25 87 193 41 42 200 63 0 137 161)
Տասնվեցական ներկայացումների տողը ստանալու համար կարելի է օգտագործել (lambda (x y) (format nil "~a~2,'0x" x y)) ֆունկցիան։
(defparameter vecstr
    (reduce #'(lambda (x y)
                (format nil "~a~2,'0x" x y))
            vec :initial-value ""))
(print vecstr)

"0C22D27F20071957C1292AC83F0089A1"

Saturday, March 16, 2013

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. Առաջադրանքի նկարագրություն

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

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

Ինչպես նաև.

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

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 գործողությունները:

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

  1. W(D) - Ընթացիկ բառում գրում է D:
  2. WH(D,H) - Ընթացիկ բառի H կեսում գրում է D տվյալը:
  3. WQ(D,Q) - Ընթացիկ բառի Q քառորդում գրում է D տվյալը:
  4. WM(D,M) - Ընթացիկ բառում գրում է D տվյալը՝ օգտագործելով M դիմակը:
  5. R(D) - Կարդում է ընթացիկ բառի պարունակությունը՝ սպասելով D տվյալը:
  6. RH(D,H) - Կարդում է ընթացիկ բառի H կեսը՝ սպասելով D տվյալը:
  7. RQ(D,Q) - Կարդում է ընթացիկ բառի Q քառորդը՝ սպասելով D տվյալը:
  8. HIT(D,A) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է միայն և միայն A հասցեում:
  9. HITH(D,A,H) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է միայն և միայն A հասցեի H կեսում:
  10. HITQ(D,A,Q) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է միայն և միայն A հասցեի Q քառորդում:
  11. MISS(D) - Որոնում է D տվյալը՝ սպասելով, որ այն հիշող սարքում չի հանդիպում:
  12. MISSH(D) - Որոնում է D տվյալը՝ սպասելով, որ այն չի հանդիպում որևէ բառի որևէ կեսում:
  13. MISSQ(D)- Որոնում է D տվյալը՝ սպասելով, որ այն չի հանդիպում որևէ բառի որևէ քառորդում:
  14. MHIT(D,A) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է մեկից ավելի անգամներ՝ A ամենափոքր հասցեում:
  15. MHITH(D,A,H) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է ավելի քան մեկ անգամ A ամենափոքր հասցեի H կեսում:
  16. MHITQ(D,A,Q) - Որոնում է D տվյալը՝ սպասելով, որ այն հանդիպում է ավելի քան մեկ անգամ A ամենափոքր հասցեի Q քառորդում:
  17. UNL(A) - A հասցեով բառը նշում է որպես ոչ ակտիվ (անվավեր):
  18. UNLH(A,H) - A հասցեով բառի H կեսը նշում է որպես ոչ ակտիվ (անվավեր):
  19. UNLQ(A,Q) - A հասցեով բառի Q քառորդը նշում է որպես ոչ ակտիվ (անվավեր):
  20. 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 դասի հետևյալ մեթոդները.

  1. writeSingle(address : Integer, data : String)address հասցեում գրում է data տվյալը, վավերականության բիթին վերագրելով S0:
  2. writeHalf(address : Integer, half : Integer, data : String)data-ն գրանցում է address բառի half կեսում: Համապատասխան վավերականության բիթը դրվում է H0 կամ H1:
  3. writeQuarter(address : Integer, half : Integer, data : String)data-ն գրանցում է address բառի quarter քառորդում: Համապատասխան վավերականության բիթը դրվում է Q0, Q1, Q2 կամ Q3:
  4. readSingle(address : Integer) : String – վերադարձնում է address հասցեով բառի պարունակությունը:
  5. readHalf(address : Integer, half : Integer) : String – վերադարձնում է address հասցեով բառի half կեսի պարունակությունը:
  6. readHalf(address : Integer, quarter : Integer) : String – վերադարձնում է address հասցեով բառի quarter քառորդի պարունակությունը:
  7. unload(address : Integer, section : Integer)address հասցեով բառի section (single, half, quarter) հատվածը նշում է որպես ոչ ակտիվ (վավերականության բիթի արժեքը դարձնում է 0):
  8. invalidate() – հիշողության մատրիցի բոլոր բառերի վավերականության բիթերին վերագրում է 0 (ZZ) արժեքը:
  9. compareSingle(data : String) : CompareResult – հիշողության մատրիցում որոնում է data՝ որոնման ժամանակ դիտարկելով միայն S0 արժեքով վավերականության բիթ ունեցող բառերը:
  10. compareHalf(data : String) : CompareResult – հիշողության բառերի կեսերում որոնում է data տվյալը՝ դիտարկելով մաին վավերականության բիթում 1 արժեք ունեցող կիսաբառերը:
  11. compareQuarter(data : String) : CompareResult – հիշողության բառերի քառորդներում որոնում է data-ն՝ նորից դիտարկելով վավերական քառորդները:
  12. 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 մեթոդում պետք է նշել այդ անսարքությունն իդենտիֆիկացնող տեքստը և որոշել, թե որտեղ է տեղադրվելու անսարք բջիջը կամ վավերականության բիթերը (դիմակի ռեգիստր, հիշող սարքի զանգված կամ վավերականության բիթերի զանգված):

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

  1. 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
  2. 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
  3. 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
  4. 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,
  5. art0, Y. Zorian, Built-In-Self-Test Technique for Content-Addressable Memories, US Patent 5107501, 1992
  6. 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
  7. art2, J. Zhao and S. Irrinki and M. Puri and F. Lombardi, Testing SRAM-Based Content Addressable Memories, IEEE Transactions on Computers, 2000
  8. art3, Zh. Xuemei and Y. Yizheng and Ch. Chunxu, Tests for Word Oriented Content Addressable Memories, Asian Test Symposium, 2002
  9. 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
  10. 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
  11. 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