二叉樹旋轉(zhuǎn)和DFA化簡(jiǎn)并行算法的研究.pdf

1、由于計(jì)算機(jī)硬件的元器件、集成度、工藝和體系結(jié)構(gòu)的發(fā)展幾乎到了極限,因此,并行處理技術(shù)成為提高計(jì)算機(jī)性能的重要手段。并行程序設(shè)計(jì)和并行編譯技術(shù)是并行處理技術(shù)的關(guān)鍵,所以并行數(shù)據(jù)結(jié)構(gòu)、并行編譯和優(yōu)化技術(shù)成為計(jì)算機(jī)科學(xué)與理論研究領(lǐng)域重要研究課題之一?；诰仃嚹Ｐ捅硎镜腄FA的極小化和二叉樹旋轉(zhuǎn)轉(zhuǎn)換算法是編譯系統(tǒng)和數(shù)據(jù)結(jié)構(gòu)中的關(guān)鍵技術(shù)。本課題主要研究基于矩陣模型表示的DFA的并行化簡(jiǎn)和二叉樹旋轉(zhuǎn)轉(zhuǎn)換算法的并行處理。這些工作對(duì)并行計(jì)算理論、并行數(shù)

2、據(jù)結(jié)構(gòu)算法設(shè)計(jì)研究有一定的理論和實(shí)踐意義。
　　 本文首先敘述了與本課題研究有關(guān)的基礎(chǔ)理論以及相關(guān)并行模型和并行數(shù)據(jù)結(jié)構(gòu);重點(diǎn)做了兩方面的研究:其一,對(duì)PRAM模型下二叉樹旋轉(zhuǎn)轉(zhuǎn)換算法進(jìn)行較為深入的研究、提出了一種PRAM模型下二叉樹旋轉(zhuǎn)轉(zhuǎn)換算法的并行處理方法。其基本思想是:引入層次矩陣,通過對(duì)二叉樹和層次矩陣的等價(jià)轉(zhuǎn)換,把對(duì)二叉樹的操作轉(zhuǎn)換成對(duì)層次矩陣的操作;由于對(duì)矩陣的并行處理技術(shù)已經(jīng)非常成熟,所以借助矩陣這個(gè)“橋梁”,最終