Geri Dön

Değişken bağımlılığı ve döngülerde paralellik

Data dependency and parallelism on loops

  1. Tez No: 19253
  2. Yazar: GÜLDEN ÇEVİK
  3. Danışmanlar: DOÇ.DR. BÜLENT ÖRENCİK
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Senkronizasyon, Veri bağımlılık analizi, Çok işlemcili sistemler, Synchronization, Data dependence analysis, Multiprocessor systems
  7. Yıl: 1991
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Compilers that automatically detect concurrency in loops use one of several synchronization methods. Some of these methods are listed below. 1) One method is to synchronize on every data dependency (random synchronization). In this method the compiler looks for data dependence that cross from one iteration to another and add an appropriate synchronization primitive for each such dependency. Random placement of synchronization is very flexible but may require many synchronization points. Depending on how the system implements synchronization, this may require too many synchronization registers. There are two methods to improve the speedup of random synchronization. One is to reorder the statements to improve overlap and the other is to eliminate covered dependencies. 2) Another method is to dev ide the loop into segments. Synchronization is added so segment S of iteration i is executed only after segment s o-F iteration i-1 is completed. The iterations are pipelined through the processors. The segments are created so all data dependency relationships stay in the same pipe-line segment or go to a lexically later segment. Pipe-line method only allows lexically forward dependencies. Random is sychronization is very flexible but optimizing this strategy is very difficult in the general case. Pipeline synchronization is more restricted, but is easier to implement. The number of synchronization points is controlled. With random synchronization the number of synchronization points may crow uncontrollably. However because of segmentation, pipelining may unnecessarily break code that need not to be synchonized. 3) A third method is to place barriers at various points of the loop. No iteration can pass beyond the barrier until all iterations reach the barrier. This stategy also allows lexically forward dependencies. When the only dependence relation is lexically forward, barrier synchronization will allow more parallelism then pipel ining. Problems with barrier synchronization occur when temporary variables are used in the loop. If a temporary variable is used in a statement and this statement is executed for all the iterations the value for the single iteration is lost. This problem can be used by using iteration local dimensional variables. A compiler that translates serial loops into concurrent loop will recognize the need for such iteration local variables. ix

Özet (Çeviri)

4) A -fourth method is to -Find sections o-F loop where communication is concentrated and make this sections in to critical sections. An advantage of critical sections is they handle backward dependencies. The compiler's goal is to insert as -Few critical sections as necessary and make them as small as possible. Because speedup is limited by the size o-F the largest critical section. When there are only a -Few lexically backward dependencies, critical sections provide as much parallelism as random synchronization. 5) Another method is to devide the loop according to a speci-Fic algorithm in to blocks and execute them -For all iterations on seperate processors. This algorithm specifies the blocks which can execute concurrently. This method also handles backward dependencies. Powerful compiler systems, such as Para-Frase Analyzer at University of Illinois, PFC at Rice University, Ptran at IBM use any of these mechanisms.Compilers that automatically detect concurrency in loops use one of several synchronization methods. Some of these methods are listed below. 1) One method is to synchronize on every data dependency (random synchronization). In this method the compiler looks for data dependence that cross from one iteration to another and add an appropriate synchronization primitive for each such dependency. Random placement of synchronization is very flexible but may require many synchronization points. Depending on how the system implements synchronization, this may require too many synchronization registers. There are two methods to improve the speedup of random synchronization. One is to reorder the statements to improve overlap and the other is to eliminate covered dependencies. 2) Another method is to dev ide the loop into segments. Synchronization is added so segment S of iteration i is executed only after segment s o-F iteration i-1 is completed. The iterations are pipelined through the processors. The segments are created so all data dependency relationships stay in the same pipe-line segment or go to a lexically later segment. Pipe-line method only allows lexically forward dependencies. Random is sychronization is very flexible but optimizing this strategy is very difficult in the general case. Pipeline synchronization is more restricted, but is easier to implement. The number of synchronization points is controlled. With random synchronization the number of synchronization points may crow uncontrollably. However because of segmentation, pipelining may unnecessarily break code that need not to be synchonized. 3) A third method is to place barriers at various points of the loop. No iteration can pass beyond the barrier until all iterations reach the barrier. This stategy also allows lexically forward dependencies. When the only dependence relation is lexically forward, barrier synchronization will allow more parallelism then pipel ining. Problems with barrier synchronization occur when temporary variables are used in the loop. If a temporary variable is used in a statement and this statement is executed for all the iterations the value for the single iteration is lost. This problem can be used by using iteration local dimensional variables. A compiler that translates serial loops into concurrent loop will recognize the need for such iteration local variables. ix4) A -fourth method is to -Find sections o-F loop where communication is concentrated and make this sections in to critical sections. An advantage of critical sections is they handle backward dependencies. The compiler's goal is to insert as -Few critical sections as necessary and make them as small as possible. Because speedup is limited by the size o-F the largest critical section. When there are only a -Few lexically backward dependencies, critical sections provide as much parallelism as random synchronization. 5) Another method is to devide the loop according to a speci-Fic algorithm in to blocks and execute them -For all iterations on seperate processors. This algorithm specifies the blocks which can execute concurrently. This method also handles backward dependencies. Powerful compiler systems, such as Para-Frase Analyzer at University of Illinois, PFC at Rice University, Ptran at IBM use any of these mechanisms.Compilers that automatically detect concurrency in loops use one of several synchronization methods. Some of these methods are listed below. 1) One method is to synchronize on every data dependency (random synchronization). In this method the compiler looks for data dependence that cross from one iteration to another and add an appropriate synchronization primitive for each such dependency. Random placement of synchronization is very flexible but may require many synchronization points. Depending on how the system implements synchronization, this may require too many synchronization registers. There are two methods to improve the speedup of random synchronization. One is to reorder the statements to improve overlap and the other is to eliminate covered dependencies. 2) Another method is to dev ide the loop into segments. Synchronization is added so segment S of iteration i is executed only after segment s o-F iteration i-1 is completed. The iterations are pipelined through the processors. The segments are created so all data dependency relationships stay in the same pipe-line segment or go to a lexically later segment. Pipe-line method only allows lexically forward dependencies. Random is sychronization is very flexible but optimizing this strategy is very difficult in the general case. Pipeline synchronization is more restricted, but is easier to implement. The number of synchronization points is controlled. With random synchronization the number of synchronization points may crow uncontrollably. However because of segmentation, pipelining may unnecessarily break code that need not to be synchonized. 3) A third method is to place barriers at various points of the loop. No iteration can pass beyond the barrier until all iterations reach the barrier. This stategy also allows lexically forward dependencies. When the only dependence relation is lexically forward, barrier synchronization will allow more parallelism then pipel ining. Problems with barrier synchronization occur when temporary variables are used in the loop. If a temporary variable is used in a statement and this statement is executed for all the iterations the value for the single iteration is lost. This problem can be used by using iteration local dimensional variables. A compiler that translates serial loops into concurrent loop will recognize the need for such iteration local variables. ix4) A -fourth method is to -Find sections o-F loop where communication is concentrated and make this sections in to critical sections. An advantage of critical sections is they handle backward dependencies. The compiler's goal is to insert as -Few critical sections as necessary and make them as small as possible. Because speedup is limited by the size o-F the largest critical section. When there are only a -Few lexically backward dependencies, critical sections provide as much parallelism as random synchronization. 5) Another method is to devide the loop according to a speci-Fic algorithm in to blocks and execute them -For all iterations on seperate processors. This algorithm specifies the blocks which can execute concurrently. This method also handles backward dependencies. Powerful compiler systems, such as Para-Frase Analyzer at University of Illinois, PFC at Rice University, Ptran at IBM use any of these mechanisms.

Benzer Tezler

  1. Tez No

    104070

    Türkiye imalat sanayiinin üretim yapısı (1973-1990) girdi-çıktı analizi

    The production structure of Turkish manufacturing industry (1973-1990) input -output analyis

    SERKAN AYDIN

    Yüksek Lisans

    Türkçe

    Türkçe

    2001

    İşletmeİstanbul Teknik Üniversitesi

    YRD. DOÇ. DR. SUAT KÜÇÜKÇİFTÇİ

  2. Tez No

    20094

    Gelişmekte olan ülkelerin dış borç sorunu ve Türkiye'nin dış borçları

    Başlık çevirisi yok

    MUSTAFA KARAGÖZ

    Yüksek Lisans

    Türkçe

    Türkçe

    1992

    Ekonomiİstanbul Üniversitesi

    Maliye Ana Bilim Dalı

    PROF.DR. ARİF NEMLİ

  3. Tez No

    393157

    Türkiye ile Körfez ülkeleri arasında dış ticaret ilişkisinin incelenmesi -Çekim modeli yaklaşımı-

    An investigation on trade relations between Turkey and Gulf countries - Gravity model approach

    OSMAN ERK

    Yüksek Lisans

    Türkçe

    Türkçe

    2015

    EkonomiGalatasaray Üniversitesi

    İşletme Ana Bilim Dalı

    DOÇ. DR. MUSTAFA BURAK GÜRBÜZ

  4. Tez No

    869564

    A new approach to corporate social responsibility: Corporate digital responsibility, analysis of Turkish banking and e-commerce sectors

    Kurumsal sosyal sorumluluğa yeni bir yaklaşım: Kurumsal dijital sorumluluk, Türk bankacılık ve e-ticaret sektörlerinin analizi

    CEYDA CİHAN AYDOĞDU

    Doktora

    İngilizce

    İngilizce

    2024

    İletişim BilimleriGalatasaray Üniversitesi

    Radyo Televizyon ve Sinema Ana Bilim Dalı

    PROF. DR. BANU MÜJDE BASKAN KARSAK

  5. Tez No

    919024

    A comprehensive analysis of Turkish sea level changes and future modeling using machine learning methods

    Türk deniz seviyesi değişikliklerinin kapsamlı analizi ve makine öğrenimi yöntemleriyle gelecek modellemesi

    ELİF KARTAL

    Doktora

    İngilizce

    İngilizce

    2024

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. ABDÜSSELAM ALTUNKAYNAK

Geri Dön