A d-algoritmus kiterjesztései

Tartalom

ELŐSZÓ
1. Bevezetés 1
2. Az értekezésbeli munka beágyazása a munkahelyi környezetébe 3
3. Az eredeti d-algoritmus és annak néhány kiterjesztése 6
3.1 Az eredeti d-algoritmus 6
3.2 Kiterjesztés többszórós jel érték elakadási hibára 6
3.3 Kiterjesztés rövidzárlati hibákra 6
3.4 Kiterjesztés szinkron szekvenciális hálózatokra 6
3.5 Kiterjesztés aszinkron szekvenciális hálózatokra 6
3.6 Kiterjesztés alkatelem késleltetések figyelembevételére és késleltetési hibákra 6
3.7 Kiterjesztés CMOS elemekből felépülő kombinációs hálózatokra 6
3.8 Kiterjesztés funkcionális szintű primitívekre 6
4. Irodalom 7
4.1 Irodalom a d-algoritmus tesztgenerálásban való alkalmazásáról 7
4.2 Irodalom a d-algoritmus egyéb alkalmazásáról 10
4.3 Egyéb hivatkozott irodalom 10

I. rész: AZ INTERAKTÍV d-ALGORITMUS
1. Bevezetés 14
2. Egy általános hibamodell 18
3. Az ember viszonya a d-algoritmushoz 29
4. Az interaktivitás 35
4.1 Az ember tevékenységei az Interaktív Módszerben 36
4.1.1 A számítógépi keresés intelligens orientálása 37
4.1.2 Intelligens hálózatparticionálás és feladatkiszabás 40
4.1.3 Részhálózat processzálására való utasításadás 43
4.1.4 Vizuális keresés 45
4.1.5 Utasításadás hibák parallel tesztelésére 48
4.1.6 Az emberi utasításadás nyelve 49
4.1.7 Mértékek a teszt generálásban 49
4.2 A számítógép tevékenységei az Interaktív Módszerben 52
4.2.1 Hibaszimuláció 54
4.2.2 Tesztgenerálás 54
4.2.3 Az Interaktív Módszer hardver háttere 55
5. A módszer alkalmazásának tényezői 57
6. Konklúzió 60
7. Irodalom 62

II. rész: A PARALLEL d-ALGORITMUS
1. Bevezetés 67
2. A parallel d-algoritmus gyorsító tényezői 68
2.1 A keresési fa processzálása párhuzamosan 68
2.2 A d-algoritmus célgép 70
2.2.1 A célgép főbb szerkezeti egységei 70
2.2.2 A célgép logikai vázlata 75
2.2.3 A d-algoritmus futása a célgépen 77
2.3 A tesztgenerálási műveletvégző célgépek 88
2.3.1 Alkatelem modellezési alternatívák és jellemzőik 88
2.3.1.1 Táblázatos modell-megadásmódok 88
2.3.1.1.1 Adattal címezhető táblázatok 88
2.3.1.1.2 Sorosan címezhető táblázzatok 88
2.3.1.2 Gráfos modell-megadásmódok 88
2.3.1.2.1 Fagráfok 88
2.3.1.2.2 Hálók 88
2.3.1.3 Algebrai modell-megadásmódok 88
2.3.1.3.1 Logikai modell-megadásmód 88
2.3.1.3.2 Aritmetikai modell-megadásmód 88
2.3.1.4 Algoritmusos modell-megadásmód 88
2.3.2 Célgépek modellek (műveletvégzések) implementációjára 88
2.3.2.1 FPLA egység 91
2.3.2.2 Táblázatkezelő keresőgépek 92
2.3.2.2.1 A táblázatos modellezés és modellkezelés kiterjesztése többkimenetű alkatelemekre 92
2.3.2.2.1.1 Többkimenetelű alkatelemek funkciójának táblázatos megadása 92
2.3.2.2.1.2 Tesztgenerálási műveletvégzés többkimenetű alkatelemek táblázatának
kezelésével 92
2.3.2.2.1.3 Keresőgépek felépítésének körvonalai többkimenetű alkatelemekre 92
2.3.2.2.2 Egykimenetű alkatelemek célgépei 95
2.3.2.2.2.1 Kereső alapgép 96
2.3.2.2.2.2 Párhuzamos keresőgép 98
2.3.2.2.2.3 Soros keresőgép 100
2.3.2.2.2.4 Homogén soros keresőgép 105
2.3.2.3 Többértékű műveletvégző egység algoritmusos modellmegadáshoz 106
3. Néhány programozott eset 108
3.1 Az AND kapu szimulációs modelljei 109
3.1.1 Egyprocesszoros számítógép, közvetlen táblázátprogramozással 109
3.1.2 Egyprocesszoros számítógép, adattal címezhető táblázat programozásával 109
3.1.3 Többértékű műveletvégző egységgel ellátott mikroszámítógép 109
3.1.4 Párhuzamos keresőgéppel ellátott mikroszámítógép 109
3.2 Egy előre/hátra következményeket számító mikroszámítógép programrészlete 109
3.2.1 A Cw mikroszámítógép egy működési ciklusának verbális részletezése 109
3.2.2 A Cw mikroszámítógép programrészlete Z80 típusú, mikroprocesszor assembly kódjában 109
4. A gyorsító tényezők hatása 109
4.1 A tesztgenerálási műveletvégző célgépek gyorsító hatása (Az AND szimulációs modell
munkaigénye) 109
4.1.1 Egyprocesszoros számítógép, közvetlen tábláz átprogramozással 109
4.1.2 Egyprocesszoros számítógép, adattal címezhető táblázat programozásával 109
4.1.3 Többértékű, művelet végző egységgel ellátott mikroszámítógép 109
4.1.4 Párhuzamos keresőgéppel ellátott mikroszámítógép 109
4.2 Egy d-algoritmus célgép eredő gyorsító hatása 109
4.2.1 Analitikus megközelítés 109
4.2.2 Struktilra alapút megközelítés 110
4.2.3 Numerikus megközelítés 110
4.3 A keresési fa párhuzamos processzálásának gyorsító hatása 110
4.4 A teljes eredő gyorsító hatás 110
5. A párhuzamos d-algoritmus hardver igénye 110
6. Konklúzió 111
7. Irodalom 112

III. rész: A DINAMIKUS d-ALGORITMUS
1. Bevezetés 115
2. A dinamikus d-algoritmus módszere 119
2.1 Alkatelem modellek 119
2.1.1 Jelaktivitás minimális aktivitásra törekvés és a tesztgenerálási modellek feltételes
volta 123
2.1.2 A jó alkatelemek modelljei 129
2.1.2.1 Konzisztencia modellek 130
2.1.2.2 d-terjesztés modellek 133
2.1.2.3 Elörekövetkezmény modellek 136
2.1.2.4 Hátrakövetkezmény modellek 137
2.1.3 A kompozit alkatelem modelljei 138
2.1.3.1 A dekompozíció módszere 139
2.1.3.2 A kompozíció módszere 141
2.1.4 A NAND kapu tesztgenerálási modelljei 144
2.1.4.1 A jó NAND kapu modelljei 145
2.1.4.2 A kompozit NAND kapu néhány modellje 148
2.1.5 Szekvenciális alkatelemek modelljeinek specialitásai 152
2.2 Rendszertechnikai kérdések 156
2.2.1 Időrelációk alkatelemek jelei között 157
2.2.2 Az időreláció lista 158
2.2.3 "Képek" 160
2.2.4 Konzisztencia folyamat
2.2.5 d-terjesztési folyamat 163
2.2.6 Folyamatábrák (algoritmusok) 165
2.2.7 A módosított Fourier-Motzkin módszer 169
2.3 Példa 171
2.4 Alkalmazások 175
3. A módszer alkalmazása késleltetési hibák esetére 179
3.1 A késleltetési hiba hatása a képződés helyén 180
3.2 A késleltetési hiba hatása a hálózat kimenetein 180
3.3 A késleltetési hiba kimutatása a hálózat kimenetein 180
3.4 Egy hálózat kimeneti jelalak érzékenysége alkatelem késleltetési hibára 180
3.5 A dinamikus d-algoritmus eltérései késleltetési hibák tesztelése esetén a beragadásos hibák tesztelése esetéhez képest 180
3.6 "Megengedhető" késleltetési hiba figyelembevétele a teszt generálásban 180
4. Szórásos alkatelem késleltetési időértékek figyelembevétele 180
5. Konklúzió 181
6. Irodalom 184

Témakörök