Geri Dön

A hill climbing algorithm with pre-processing and a column replication method for variation tolerant logic mapping problem

Nanodizinlerde varyasyon toleranslı mantıksal haritalama için ön aşamalı bir tepe tırmanma algoritması ve sütun kopyalama metodu

PDF İndir

  1. Tez No: 472847
  2. Yazar: FURKAN PEKER
  3. Danışmanlar: YRD. DOÇ. DR. MUSTAFA ALTUN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Elektronik Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 80

Özet

Nano anahtarlamalı dizinler tasarım özellikleri ve boyutları ile gelen yüksek hız ve düşük güç tüketimi özellikleri sayesinde yeni gelişen teknolojiler arasında öne çıkmaktadırlar. Bu özelliklerine ek olarak, genellikle geleneksel litografi yöntemlerine göre daha hızlı ve ucuz yöntemler ile üretilmektedirler. Öte yandan, sahip oldukları küçük boyutlar ve genellikle kendiliğinden kurulma teknolojileri ile gerçeklenmeleri, bu yapıların hatalara ve varyasyonlara duyarlılığını geneleksel litografi yöntemlerine oranla yüksek seviyelere çekmektedir. Yüksek hata ve varyasyon oranları, bu etkenlere karşı tolerans teknikleri geliştirilmesi ihtiyacını doğurmuştur ve nano-anahtarlamalı dizinler için önemli bir tasarım parametresi haline gelmiştir. Literatürde bu tolerans problemi farklı etkenlere göre farklı yöntemler ile incelenmiştir. Kendiliğinden kurulma yöntemleri olasılıksal doğalarından ve tasarım boyutlarının küçüklüğünden dolayı yüksek hata oranları ile nano-anahtarlamalı dizinleri gerçeklerler. Bu hatalar, nano-anahtarlamalı dizin üzerindeki bir kesişim noktasında oluşturulmak istenilen cihazın (diyot, FET veya 4-uçlu anahtar) veya bu olası cihazların ararındaki tel bağlantılarının işlevselliğini bozmaktadırlar. Bu hatalar, bir cihazın her zaman açık veya kapalı olarak çalışması şeklinde veya bir bağlantı telinin kopması şeklinde olabilir. Dolayısıyla, üretilen bir nano-anahtarlamalı dizinde kullanılacak cihazların seçimi, devrenin işlevselliği açısından kritik anlamda önem taşır. Hatalı cihazlara ek olarak, devrenin işlevselliğini bozmayan fakat çalışma performansını önemli ölçüde etkileyen varyasyonlar nano-anahtarlamalı dizinlerde mevcuttur. Hatalar, bu varyasyonların aşırılığından kaynaklaran durumlar olarak da tanımlanabilir. Bir nano-telin çapındaki aşırı varyasyon bu telin açık devre olarak çalışmasına sebep olacak seviyelere gelmesine sebep olabilir. Bu durumda söz konusu tel hatalı olarak değerlendirilir ve hata toleransı teknikleri ile kullanımından kaçınılır. Öte yandan, aşırı seviyede olmayan varyasyon değerleri işlevselliği bozmazken, devrenin çalışma performasını önemli ölçüde etkileyebilir. Nanotel boyutlarının sayılı atom çaplarına yaklaşması ile tek bir dopant atom eksikliği bile yarıiletken bir cihazın performans parametrelerini etkileyebilmektedir. Bununla beraber nanotel, oksit kalınlığı vb. tasarım parametrelerinde oluşabilecek boyut varyasyonları da direnç ve kapasite değerlerini önemli ölçüde etkileyebilmektedir. Dolayısıyla, gecikme ve güç tüketimi değerleri nano-dizin üzerinde kullanılan cihazlara göre saçınık bir karaktere sahip olmaktadır. Bu etkenlerin sonucu olarak varyasyon toleransı tekniklerinin geliştirilmesi ihtiyacı doğmuştur. Bu teknikler, mantık fonksiyonunun anahtarlamı nano-dizin üzerine performans parametreleri göz önüne alarak en iyi şekilde yerleştirilmesini amaçlamaktadır. Varyasyon toleranslı mantıksal haritalama adı altında literatürde farklı yöntemler sunulmuştur. Fonksiyon matrisinde, satır girişleri fonksiyon değişkenlerini, sütun çıkışları ise fonksiyon çarpımlarını ifade etmektedir. Eğer bir fonksiyon girişi, çıkış çarpımında bulunuyorsa bu satır ve sütunları kesişim noktalarında bir anahtarı ifade edecek şekilde 1, aksi durumda ise 0 bulunur. Gerçeklenmek istenilen mantıksal fonksiyona bağlı olarak, nano-anahtarlamalı dizinde bulunan cihazların önemli bir kısmı zaten kullanılmamaktadır. Dizin üzerindeki giriş ve çıkışların sıraları değiştirilerek gerçeklenecek mantıksal fonksiyonun işlevselliği değiştirilmeden, farklı cihazlar kullanılabilir. Mantıksal fonksiyonun değişken girişlerinin ve çarpım çıkışlarının konumlarının nano-anahtarlamalı devre üzerine yerleştirilmesi işlemi mantıksal haritalama olarak adlandırılır. Fonksiyon matrisinin bu değiştirilebilirlik özelliği hata toleransı ve varyasyon toleransı tekniklerinin mantıksal haritalama ile gerçekleştirilebilmesini sağlamaktadır. Varyasyon toleranslı mantıksal haritalama işlemi için fonksiyon matrisi ile beraber nano-anahtarlamalı dizin matrisinin her bir kesişim noktasının aktif bir cihaz olarak kullanıldığı durumda çıkışta oluşan gecikmeye katkısı bilinmelidir. Her bir kesişim noktasının gecikmeye katkısı ile oluşturulan, nano-anahtarlamalı dizin ile aynı boyuttaki matrise varyasyon matrisi adı verilmektedir. Varyasyon toleranslı mantıksal haritalama işlemi, fonksiyon matrisinin girişlerinin (satırlar) ve çıkışlarının (sütunlar) varyasyon matrisi üzerine en uygun şekilde sıralanması ile gerçekleşir. Varyasyon matrisinin elde edilmesi için üretilen devrenin gecikme testinden geçirilmesi gereklidir, dolayısıyla zaman ve maliyet gerektirir. Literatürde varyansyon toleranslı mantıksal haritalama yöntemleri genel anlamda iki amaca yönelik tasarlanmışlardır. Bunların ilki, en yüksek gecikmeye sahip hattın gecikme değerinin olabildiğince düşük olmasıdır. ˙Ikincisi ise en yüksek gecikmeye sahip hat ile en düşük gecikmeye sahip hat arasındaki gecikme farkının olabildiğince küçük olmasıdır. ˙Ikinci amaç gecikmeler arasındaki farkı azaltarak devrenin gecikme varyansını azaltmaya çalışmaktadır fakat bunu yaparken bazı durumlarda yüksek gecikmeye sahip kesişim noktalarını kullanmaktadır. Devrenin en yüksek çalışabileceği hızı en yüksek gecikmeli hat belirlediğinden, önerilen algoritma sadece ilk amaca odaklanarak tüm hesaplama gücünu daha düşük gecikmeye sahip bir haritalama elde etmek için tasarlanmıştır. Ayrıca, kullanım alanı daha geniş olan ve ilgi gören FET tipi nano-anahtarlamalı dizinler için çalışılmıştır. FET tipi nano-anahtarlamalı dizinlerde her bir sütun mantıksal fonksiyondaki bir çarpımı ifade eder. En yüksek gecikmeli durumda bu hatlardan sadece birisi aktiftir, bu durumda devreden en az akım akacağından gecikme yüksek olacaktır. Söz konusu en yüksek gecikmeli hattın sahip olduğu gecikme, o hat üzerinde aktif olarak kullanılan kesişim noktalarındaki cihazların çıkış gecikmesine olan katkılarının toplamıdır. Fonksiyon matrisinde '1'e denk gelen kesişim noktaları FET, '0'a denk gelen kesişim noktaları ise kısa devre tel olarak çalışır, dolayısıyla Hadamart çarpımı devrenin haritalama sonrasında sahip olacağı performansı ifade etmekte yeterlidir. Özetle, fonksiyon matrisi ile varyasyon matrisinin Hadamart çarpımının en yüksek toplamlı sütunu, en yüksek gecikmeyi ifade eder. Varyasyon toleranslı mantıksal haritalama işleminde, oluşacak en yüksek gecikmeli sütunun değerinin en düşük değere getirilmesi amaçlanmaktadır. Bu çalışmada varyasyon toleranslı mantıksal haritalama problemini FET tipi nano-anahtarlamalı dizinlerde çözmek için bir tepe tırmanma algoritması önerilmiştir. Bu algoritma 2 ön aşama, 2 arama olmak üzere 4 tip algoritmanın birlikte çalışması ile oluşturulmuştur. Ön aşama algoritmaları literatürdeki diğer arama algoritmalarıyla da kullanılabilirler. Bu yapıları ile algoritma-bağımsızdırlar ve ön aşaması oldukları algoritmaların performanslarını iyileştiricidirler. Tepe Tırmanma algoritması, sabit bir sütun sıralaması için satır sıralamalarını arayarak iyileştirilmiş sonuçlar bulmaya çalışır. Üretim aşamasında pek çok etken beklenen yapıda sapmalara sebep olduğundan, simulasyonlar için her bir kesişim noktasında oluşacak gecikme değeri rastgele bir Normal dağılımlı sayı olarak modellenmiştir. Normal dağılım için beklenen ortalama değer ve standart sapma değerleri üretim tekniğine bağlı olarak belirlenir ve varyasyon matrisi bu dağılımdan alınan rastgele sayılar ile oluşturulur. Simulasyonlarda yüksek ve düşük gecikmeli değerler arasında 10-20 kat fark olacak şekilde ortalama değer ve standart sapma değerleri belirlenerek yüksek varyasyon durumları incelenmeye çalışılmıştır. Önerilen algoritmanın ilk adımı olarak bir fonksiyon matrisi indirgeme yöntemi önerilmiştir. Her bir fonksiyon matrisi sütununun, her bir varyasyon matrisi sütununda alabileceği değerler rahatlıkla hesaplanabilir. Burada referans olarak en yüksek sayıda '1'e sahip olan sütunun alabilceği en küçük değeri parametre olarak kullanabiliriz, çünkü bu değer verilen fonksiyon ve varyans matrisi çifti için ulaşılabilecek en iyi performans değeridir. Eğer, diğer herhangi bir sütunun alabileceği en yüksek değer, performans değerin altındaysa bu sütun hesaplaması gereksiz bir sütun olarak kabul edilebilir. Söz konusu sütunun en yüksek gecikmeye sahip olması mümkün olmadığından, arama algoritmasının her seferinde bu sütun için işlem yapmasına gerek yoktur. Tüm hesaplaması gereksiz sütunlar bulunduktan sonra fonksiyon matrisinden silinerek indirgenmiş, performans eşdeğeri bir matris elde edilir. ˙Indirgeme işlemi sadece en yüksek gecikmeyi iyileştirmeye çalışırken geçerlidir ve bu amaçla çalışan tüm algoritmaların bir ön aşaması olarak kullanılabilir. Fonksiyon matrisinin sütunlarının sahip oldukları '1' sayıları arasındaki fark arttıkça bu yöntemin iyileştirme oranı da artmaktadır. Bazı matrislerde hiç ingirgeme yapılamazken, bazı bençmarklarda %72'lere kadar sütun indirgenmesi yapılabilmektedir. Bu oran kullanılan algoritmanın sütun işlemi yoğunluğuna göre farklı oranlarda iyileştirme sağlar. %76'lara varan zaman iyileştirmesi bu yöntem ile sağlanmıştır. ˙Ikinci adım olarak, bir sütun sıralaması elde edilerek Tepe Tırmanma algoritmasının başlangıç noktası belirlenir. Bu sıralama için, her bir fonksiyon sütununun, her bir varyans sütununda alabileceği en düşük değerler belirlenir. Bu noktadan sonra, en kritik (en yüksek sayıda '1'e sahip) fonksiyon sütunundan başlanarak, her bir fonksiyon sütunu en düşük değeri alabileceği varyans sütununa atanır. Daha önce kullanılan bir varyans sütunu bir daha kullanılamaz. Bu ilk haritalama konumu, aynı çalışma süresinde rastgele başlangıç noktasına göre %2-3 dolaylarında daha başarılı sonuçlar alınmasını sağlamıştır. Arama algoritması olarak kullanılan Tepe Tırmanma algoritması, sabit bir sütun sıralaması için satır sıralamalarını değiştirerek alabileceği en iyi sonuca ulaşmaya çalışır. Artık iyileştiremediği bir noktaya ulaştığında ise yeni bir sütun sıralaması bularak aramaya tekrar başlar. Bu yeni sütun bulunması işlemi arama algoritmasının ikinci kısmı olan sütun yeniden haritalama kısmıdır. Tepe Tırmanma algoritması arama sırasında, her performans testinde hangi sütunun en yüksek gecikme değeri verdiğini kaydeder. Sütun yeniden haritalama algoritması çalışacağı zaman bu bilgiyi Tepe Tırmanma algoritmasından alır ve en fazla sayıda en yüksek gecikme değerini vermiş sütunun yerine fonksiyon matrisinin düşük '1' sayısına sahip sütunlarından biri ile yeri değiştirilir. Sütun yeniden sıralama algoritması çalıştıktan sonra Tepe Tırmanma algoritması tekrar çalışır ve bu döngü durma parametrelerinden birine ulaşılıncaya kadar devam eder. Kullanılan bu method literatürde verilen algoritmalara göre özellikle yüksek boyutlu matrislerde (24x24, 48x48) %15'lere yaklaşan iyileştirme oranlarına sahiptir. Düşük boyutlu matrislerde (6x6) ise benzer iyileştirme oranlarına rağmen 5-20 kat daha hızlı çalışmaktadır. Varyasyon toleransı için önerilen Tepe Tırmanma algoritmasının ek bir kullanımı olarak, problem tanımını değiştirerek bu algoritmanın hata toleransı işlemlerini de gerçekleştirmesi sağlanmıştır. Bunun için varyasyon matrisine hatalı kesişim noktaları eklenerek bu noktaların gecikme değerleri beklenen gecikme değerlerinin 100 katı olarak verilmiştir. Bu durumda çalışan algoritma çok yüksek gecikmeye sahip kesişim noktalarını tolere etmeye çalışacağından hata toleransı yapacak şekilde çalışmaya başlamış olur. Bu şekilde yapılan simülasyonlarda %40 kesişim noktası yoğunluğuna sahip rastgele matrislerde %15-30 hata oranları tolere edilebilmiştir. Bu çalışmada kullanılan stanadart bençmark seti için %5-20 hata oranları tolere edilebilmiştir. Son olarak, üretimde oluşacak varyanslara farklı bir yaklaşım olarak, alandan taviz vererek sütun kopyalama yöntemi kullanılmıştır. Gecikmelere sebep olan etkenin ağırlıklı olarak dirençlerden kaynaklı olduğu ve nano-dizinin iç kapasitelerine göre daha yüksek bir çıkış kapasitesi sürüldüğü varsayıldığında, aynı anda iki veya daha fazla sütunun aktif olması daha yüksek akım akışına fırsat vererek gecikmelerin iyileştirilmesini sağlayacaktır. Birbirinin kopyası olarak haritalanmış iki sütun daima aynı anda iletimde olacağından, tek başına bir sütunun sebep olacağı gecikmeden çok daha düşük bir gecikme değeri elde edilebilir. Buradaki problem hangi sütunların ne kadar kopyalanacağıdır. Öyle ki, her bir sütun daha fazla alan kullanımını ve güç tüketimini ifade etmektedir. Bu noktada, üretim yönteminin ortalama değer ve standart sapma parametrelerinin bilinmesi hedef bir performans değeri elde edilmesi için yeterlidir. Her bir fonksiyon sütununun çıkış performansı, o sütunun sahip olduğu '1' sayısına ve üretim yöntemi parametrelerine bağlı olarak bir Normal dağılım olarak ifade edilebilir (Normal dağılımların toplamı). En fazla sayıda '1'e sahip fonksiyon matrisi sütununun toplam ortalama değeri, hiç varyans olmasaydı elde edilecek performansa denk geldiğinden bir performans parametresi olarak alınabilir. Öte yandan, bu ortalama değerin 3 standart sapma aşağısı %99.7 ihtimalle alacağı en düşük değeri ifade eder. Bu değer, bir arama algoritması kullanıldığında elde edilebilecek en iyi performansı ifade ettiğinden diğer bir performans parametresi olarak kullanılabilir. Bu yöntemin en büyük avantajı her bir kesişim noktası için gecikme testinin yapılmasına gerek olmaması ve herhangi bir arama algoritması kullanılmamasıdır. Fakat, alan ve güç tüketimi artışı bu yöntemin dezavantajıdır. Bazı matrislerde alan ve güç tüketimi istenilen parametrelere ulaşmak için %100 seviyelerine çıkarken, bazı bençmarklarda sadece %5 alan artışı yeterli olabilmektedir. Fonksiyon matrisi indirgeme yöntemine benzer olarak, sütunlarda bulunan '1' sayısının saçınık olması bu yöntemden daha fazla verim alınmasını sağlamaktadır Sonraki çalışmalarda bu algoritmaların farklı performans parametrelerine göre düzenlenerek çok-amaçlı hale getirilmesi sağlanması planlanmaktadır. Ayrıca verilen arama algoritmasında iyileştirmeler yapılması ve yeni yaklaşımsal yöntemler eklenmesi ile daha iyi gecikme performansı sonuçlarına ulaşılması sağlanabilir. Ayrıca tüm bu yöntemler diyot ve 4-uçlu mantıksal tasarım yaklaşımları için benzer olarakyeniden oluşturulabilir.

Özet (Çeviri)

Nano-crossbar arrays are generally manufactured with faster and less costly methods than traditional tow-down lithography methods. However, due to very small device sizes, there is less control over these manufacturing processes. Therefore, crossbar arrays suffer from process variations and defects with considerably higher rates than lithography processes. This variations makes performance of any manufactured array unpredictable and worse than expected. As a result, variation and/or defect tolerant logic mapping algorithms needed to be developed for this problem. In this work, I focus on maximum delay increase due to process variations and focused on optimize this objective. Firstly, a matrix reducing method is proposed to achieve better runtimes for any variation tolerant logic mapping algorithm for the maximum delay optimization. In this method, we find columns which have very low (or no) probability to become the worst case on each performance test and reduce matrix bu deleting these columns. Deleted columns mapped randomly on final mapping. Note that this reducing method is algorithm independent, which means that it can be implemented on any variation tolerant logic mapping search algorithm with same performance criteria. As a variation tolerant logic mapping scheme, a Hill Climbing row search with column re-ordering (as restart points to search) algorithm is proposed. This method restarts Hill Climbing row search after reaching an unoptimizable point by re-ordering columns with data gathered on row search, until any of the stop criteria reached. Also, a greedy initial column ordering algorithm explained and matrix reducing method is applied to Hill Climbing algorithm as pre-processing phase. As an extension for our Hill Climbing algorithm on variance tolerance, we modeled variation tolerant logic mapping problem as defect tolerant logic mapping problem by adding defective crosspoints on array matrix and run our algorithm with these defects. Our algorithm successfully tolerate different defect rates for random matrices or benchmark circuits. Lastly, as a probabilistic approach by process parameters, a worst case route replication method is proposed. This method do not use any search algorithm or need any individual crosspoint characteristic testings, which are time and resource consuming processes. This approach uses area and power overhead as trade-off values, while power-delay product is generally having decreasing characteristics. We simulated all proposed algorithms and methods on Simulation Results Section. We explained some algorithms from the literature and compared our Hill Climbing with Column re-ordering algorithm with these. Our algorithm achieves performance outputs up to 15% and runtimes up to 150-400 times better than methods on the literature, depending on the array size. As a inspection of matrix reducing method, we applied this method on different benchmarks and algorithms to compare time optimization results. Up to 72% time improvement is achieved for certain benchmarks and different algorithms by this reducing approach. Our algorithm achieved 15-30% defect tolerance for random arrays with 40% crosspoint ratio and 5-20% defect tolerance for our benchmark set. We discuss to implement this methods for different nano-crossbar array types like diode or 4-terminal as future work. Also, we aim to improve presented algorithms since both matrix reducing and initial column mapping methods are in their preliminary states in this work.

Benzer Tezler

  1. Tez No

    743128

    Mimari konum planı ön tasarımında bir yapay zeka uygulaması

    An artificial intelligence application in the pre-design of the architectural location plan

    ALİ EMRE ÇERÇİ

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    MimarlıkToros Üniversitesi

    Mimarlık Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ŞAFAK EBESEK

  2. Tez No

    709824

    Heuristic algorithms for solving chemical shift assignment problem in protein structure determination

    Sezgisel algoritmalar ile protein yapı belirlemesindeki kimyasal kayma atama probleminin çözümü

    EMEL MADEN YILMAZ

    Doktora

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AYŞE ŞİMA UYAR

    PROF. DR. PETER GÜNTERT

  3. Tez No

    567674

    Dynamic allocation of physical registers in simultaneous multi-threading processors for performance, power, fairness, and quality of service

    Eş zamanlı çoklu işparçacıklı işlemcilerde performans, güç, adalet ve servis kalitesi için fiziksel yazmaçların dinamik ayrılması

    HASANCAN GÜNGÖRER

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÜRHAN KÜÇÜK

  4. Tez No

    908543

    JAYA algoritmasının bir yerel arama yöntemi ile iyileştirilmesi

    Optimization of JAYA algorithm with a local search method

    YACOUB KADAR HASSAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKütahya Dumlupınar Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÜRCAN YAVUZ

  5. Tez No

    401849

    A memory-integrated artificial bee algorithm for heuristic optimisation

    Başlık çevirisi yok

    TUĞRUL BAYRAKTAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolUniversity of Bedfordshire

Geri Dön