Yeni bir hata değişik delta ağ maddeli arttırılmış delta ağı (ADA)
Başlık çevirisi mevcut değil.
- Tez No: 75538
- Danışmanlar: DOÇ. DR. MEHMET BÜLENT ÖRENCİK
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 1998
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Kontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 138
Özet
Yapılan tez çalışmasında öncelikle oldukça güncel olan paralel bilgi sistemlerinin en önemli elemanlarından biri olan arabağlaşım ağlarından özellikle çok işlemcili sistemlerde kullanılan çok katlı arabağlaşım ağla rı incelenmiştir. Bu incelemenin ardından Kar-Değiştir (Shuffle-Exchange) ağları üzerinde geliştirilmiş bir tek hata bağışık ağ modeli olan Arttırılmış Kar-Değiştir Ağlarının (Augmented Shuffle- Exchange Network- ASEN) ek donanımı ve adaptif yönlendirme algoritması örnek alınarak axb bağlaşma elemanlarından oluşan delta ağları tek hata bağışık kılınmıştır. Elde edilen bu yeni hata bağışık delta ağ modeli Arttırılmış Delta Ağı (ADA) olarak adlandırılmıştır. ADA da ASEN gibi tek hata bağışıktır. Ancak ADA'da ASEN'de kullanılan bağlaşma elemanı hata modeli yerine bağlantı hata modeli olarak seçilmiştir. Kullanılan ek donanım, ilk ve son kat dışındaki katlarda kullanılan arabağlaşım elemanlarının her birine yardımcı bir giriş ve çıkış bağlantısı eklemeyi gerektirir ve her katta aynı varış alt kümelerine uzanan eşlenik bağlaşma elemanı alt kümeleri ve bir sonraki katta aynı bağlaşma elemanına bağlı a-eşlenik bağlaşma elemanları kavramım getirir. Yardımcı bağlantılar, aynı kattaki eşlenik alt küme bağlaşma elemanlarım birbirine bir çevrim oluşturacak şekilde bağlamaya yararlar. Eğer bir bağlaşma elemanı bir sonraki katla arasında bulunan bir bağlantı hatası veya meşgul bir bağlantı yüzünden bir isteği işleyemiyorsa bu isteği yardımcı çıkış bağlantısını kullanarak çevrimde bir sonraki bağlaşma elemanına gönderir. Böylece bu eleman, aynı yönlendirme bilgilerini kullanarak bir sonraki katta başka bir bağlaşma elemanına bağlantı kurar. Çalışmada önce bu ağın donanımına ilişkin bağıntılar çıkarılmış, ardından arabağlaşım ağı üzerinde devre bağlaşma metodu ve küresel bir ağ saati ile senkron çalışma modu kullanılarak bu ağ üzerinde kullanılabilecek hata sezici bir bağlaşma elemanı sunulmuştur. İstenen çıkış bağlantılarında oluşabilecek eşlik hatalarında geçici bağlantı hatalarını elemek üzere ikinci kere eşlik denetimi yapılır. Kalıcı hata (ikinci kere üst üste bulunan eşlik hatası) bulunması halinde giriş bağlantısından daha önceki bir zamanda alınan veri sözcüğünün serbest ise yardımcı çıkış bağlantısına gönderilmesi istenir. Bu nedenle her giriş bağlantısında gelen veri sözcüklerinin atandığı bir tampon tutulur. Hata sezmek ve yardımcı çıkış bağlantısına yönlendirme için getirilen iyileştirmelerin bir gereksinimi olarak ardışıl katlardaki birbirine bağlı bağlaşma elemanları, veri transferini bir takım protokol işaretleri ile gerçekleştirirler. Aynı yapı, asenkron çalışma modu için de uygundur. Sezilen hatalar ağın üstünde yer alan GMU (Global Management Unit)'ya raporlanır. GMU ile bağlaşma elemanı arasındaki LinkError hattı hariç diğer işaret hatlarında da hata oluşabileceği varsayılmış ve bu hataların da sezilebilmesi kotarılmıştır.
Özet (Çeviri)
With the rapid advances in VLSI technology, relatively inexpensive hardware systems and subsystems are now available. The result has been greater use of multiple-processor system designs that employ processing elements, operating in parallel, to achieve high levels of computational power. Parallel or distributed sytems can be divided into two categories: Multiprocessors and multicomputers. The main difference between two lies in the level at which interactions between the processors occur. A multiprocessor system must permit all processors to directly share main memory. However, in a multicomputer system, each processor has its own local memory. Sharing between the processors occurs at a higher level, through a complete file or data set; a processor can not directly access another processor's local memory. An interconnection network (IN) is a complex connection of swich elements and links that permits data communication between processors and memories or between the processors. An IN has four functional characteristics to be considered during its design. These are timing, switching, overall control and topology. The timing control of an IN can be either synchronous or asynchronous. Synchronous systems are characterized by a central global clock that broadcasts the clock signal to all devices in the IN so that they operate in a lockstep fashion. Asynchronous systems support independent operation of the devices without a global clock. An IN transfers data using either circuit swiching where once a device is granted a path in the IN, it will occupy that path for the duration of the data transfer, or packet switching where the information is broken into small packets that individually compete for a path in the IN. Based on the overall control of the network, an IN may be classified as centralized or decentralized. In centralized control, a global controller receives all requests and transmits the messages in the IN. In a decentralized system, requests are handled independently by different devices in the IN. The topology of an IN is a graph that shows processors (nodes) as vertices and links between them as edges. Topologies are classified into two categories: Static and dynamic. In static topologies, the connections between two processors are passive and these dedicated links can not be reconfigured in order to be used as directly connected to other processors. Static topologies are used in multicomputer systems and some examples of static topologies are star, ring, tree, hypercube. In dynamic topologies, the active switching elements in the IN can be organized to establish dynamic connections between processors or processors/memories. Dynamictopologies are used in multiprocessor systems and some examples of dynamic topologies are shared-bus, crossbar, single-stage and multistage interconnection networks. This study is focused on delta network which is a type of multistage interconnection network (MIN). So, it is worth to investigate the place of MINs among dynamic topologies. A shared-bus interconnection is the least complex IN, but it does not allow more than one processor at a time to access a shared memory. A large number of processors means a long wait for the bus. A crossbar supports all possible distinct connections between the processors and memories simultaneously. However, the cost of a such a network is 0(n2 ) for connecting N inputs to N outputs. For a system with hundreds of processors, the cost of such an IN is prohibitively high. The cost and performance of MINs hit a reasonable balance between those of a shared-bus and crossbar. Design, analysis and development of MINs during last decades have made them the most current technology. It is indispensable to study switching element structure and interconnection function that is used to organize links between two stages before examining MINs. The most commonly used swich element are 2x2 and 4x4 crossbar switches. However, it is possible to use a axb switch within MINs. A switch element must handle request incoming from its input ports for routing these requests and informations to its output porte using destination bits as routing tags. Another role of a switch is to arbitrate between requests that compete for the same output port. Interconnection functions are multiple, however the most used of them are cube and shuffle- exchange. Examples of MINs are generalized cube, shuffle-exchange, banyan, S/W banyan, delta, benes, baseline, omega, butterfly, data manipulator,etc. In this study, three of them (generalized cube, shuffle-exchange and delta networks) are investigated wsth more details; because generalized cube network is the most commonly used IN in SIMD/MIMD parallel systems, shuffle-exchange network is the network which is made fault-tolerant with implementation of Augmented Shuffle-Exchange Networks (ASENs) whose the hardware and routing algorithms are taken as model to make fault-tolerant delta networks and delta network is the subject of tins study. Another important issue while designing INs is deciding its routing algorithm for message. The routing is simply determining a path between a source and destination in order to transfer an information. There are different classification of routing such as central / distributed; deterministic(oblivious)/adaptive and minimal/nonminimal. Currently, the most important feature intended for routers is being reconfigurable in order to ran different routing algorithms on different topologies. It means that a router must be programmable and flexible. A router must also determine the output port in a fast manner. Available flexible routers are lookup tables and dedicated processors. Dedicated processors are slow as they run algorithms sequentially and expensive. Lookup tables are fast but require big amount of memory to register paths for reaching each destination. A new alternative to flexible router is the bit- pattern associative router. This router has an associative memory that holds bit patterns to compare with destination bits in order to specify the output port So, it isas fast as lookup tables and require less amount of memory as number of bit patterns are of degree of network size and not the number of destinations. Fault tolerance is an important feature for all parallel/distributed systems. It is the ability that the system continues to operate despite of failure(s) in some part(s) of it. Most of MINs provide unique path between any source/destination pair; so they have to be enhanced for fault tolerance. A fault-model captures the assumed effects of physical failures on the operation of a system. Three fault models are used for MINs: the stuck-at fault model, the link fault model and the switch fault model. In the stuck-at fault model, a failure causes a switching element to remain at a particular state regardless of the control inputs given to it, thus affecting its ability to set up proper connections. The affected switch element can be used to set up paths if the stuck-at state is alos the required state. In the link fault model, a failure affects an individual link of a switching element, leaving the remaining part of the switch operational. In the switch fault model, the strongest of three, a failure makes a switch totally unusable. There are several approaches for providing fault tolerance of MINs. These are coding (error detecting / correcting parity, interlaced parity and CRC codes), partial redundancy (extra stage or column), replication (duplex and TMR), dynamic full access, multiple networks and multiple transmissions. Most of them are based on using extra hardware for providing alternative paths. An effective technique to alleviate the problems posed by unique-path MDSfs that is applicable to a broad class of shuffle-exchange and topologically equivalent networks is presented. It is an augmentation technique and implements Augmented Shuffle-Exchange Networks (ASENs). Its objective is to achieve single-switch fault tolerance in all stages, including the first and the final stage; the ability to reroute without backtracking; on-line repairability of faulty components and low switch and link complexity. All formulas and equations given for constructing an ASEN are given based on shuffle-exchange networks made of 2x2 switches in the paper that presents ASENs. To achieve fault tolerance in ASENs, the fact that mere are subsets of switches in each stage which lie on paths leading to the same subset of destinations is exploited. All the switches in a given stage which lead to the same subset of destinations comprise a 'conjugate subset of switches'. The switches in each stage are partitioned into several conjugate subsets. In each conjugate subset of switches, there are several pairs of switches called 'conjugate pairs of switches'. The switches in such a pair are connected to the same switches in the next stage. The scheme for creating multiple paths is based on connecting the switches belonging to a conjugate subset by using additional links to form loops. The vertical links, which are used to connect switches in the same stage, are called 'auxiliary links'. If a switch is not able to process a request for connection because of a faulty switch in the next stage or because of a busy link, it can route that request via its auxiliary output link to the next switch in the loop.ASEN handles also switch failures in the initial and final stages. A switch failure in initial stage disconnects the sources attached to that switch from the rest of the network. Similarly, a switch failure in the final stage disconnects the destinations attached to that switch. To attain fault tolerance in these stages, each source and each destination must be provided with at least one additional I/O port, so they can be connected to at least two distinct switches. So, a 2x1 multiplexer is placed at each input link of stage 0 and each source is connected to two distinct multiplexers. To provide additional connections to the destinations, the N/2 (N: the number of destinations) switches in the final stage of the MOST are replaced with N 1x2 demultiplexers. Each destination is directly connected to two demultiplexers. In order to obtain an ASEN after all these augmentation schemes, each loop is divided into smaller loops subject to the condition that no two swiches in a given loop form a conjugate pair. By this way, the obtained network has not only single fault tolerance but also certain properties that facilitate on-line repair and maintenance. If this network has the maximum number of switches per loop within the mentioned constraint, it is called ASEN-Max. It is possible to design ASENs with smaller loops than those of ASEN-Max and yet retain the property of single fault tolerance. In general, an ASEN in which the number of switches in a loop in stage i is equal to Min(2n~2~\ AT) is called ASEN-K. It is economically attractive to have all the loops be of the same size so that only one type of replacement board is needed. This is an advantage of ASEN-K networks over ASEN-Max. The adaptive routing algoritm given for ASENs assumes that sources and switches have the ability to detect faults in the switches to which they are connected. Off-line fault diagnosis techniques are inadequate with the switches making the routing decisions because fault information is required by the individual switches at the time they process a request. So, it is necessary to design switching elements capable of detecting faults in adjoining switching elements as they occur and concurrently with normal operation. In this study, a new fault-tolerant delta network called Augmented Delta Network (ADA) is presented. ADA imitates the extra hardware of ASEN to attain fault tolerance. But, it has a different fault model based on link fault instead of switch fault. The reason of the ability of using ASEN as a model to ADA is that both uses shuffle interconection function between any two stages of the network. The first step of defining an ADA is to adapt formulas for obtaining conjugate switches and loops in an ASEN formed of 2x2 switch element Additionally, as a delta network can use any axb switch element, this formulas and relations must be a function of a and b. Then, the construction of an ADA-Max and ADA-K with (a+l)x(b+l) switch elements, auxiliary links, loops, axl multiplexers to which source nodes are connected and l xb demultiplexers at the end of which destination nodes are attached is completed. The second step in this study is to design switch elements capable of detecting link faults and reporting them to a Global Management Unit (GMU) which manages fault location and recovery. There are 2 wire between GMU and each link of the switch element: One transmits the signal indicating that an error has occurred (LinkError),the other transmits the signal indicating error code (ErrorCode). It is assumed that by means of these informations, GMU knows the link mat has reported them, so it is able to manage link fault As switching method of the network, circuit switching method is selected; because by this way, it is easier to inform a source from a link fault occurred along the established path. When a source has any data to transmit, it raises its Request signal to 1 from 0. This corresponds to the path establishment phase and during this phase, only destination bits are transmitted as a data word because they are essential in routing. This request is propagated along the path and is retained at 1 during the transfer of whole data block. After path establishment phase, only information bits are transmitted in data words. For fault detection, a parity bit is generated by the source and propagated along the path together with data bits for each word in order to detect an odd number of faults. Every input link in a switch element has a parity checker in order to detect a parity error. If a parity error is detected, it is informed to the connected output link of the previous stage by ParityError signal. Then, the output link sends the last word again in order to eliminate a transient link fault within time. If a parity error is reported for the second time, then the both the input link that detects fault and the output link that receives parity error informs GMU with related error code. Besides ParityError, there are two other protocol signal used for handshaking between adjacent switch elements before transferring data; because the routing in ADA is not straightforward and there is a possibility of routing data to the auxiliary output link if the corresponding input link detects and reports a parity error. So, this data must be stored in a buffer as it can be used later. The protocol signals are useful at this point: ready signal sent toward output link indicates that data in the input link buffer is no more useful. So, a new data word can be accepted and it is driven by the output link with DataAvailable signal. This signalization is convenient for asynchronous operation mode; but for simplicity and in order to draw ASM diagrams related to input and output links, synchronous mode is preferred and it is assumed that a global network clock ensures synchronization. In the fault model, it is assumed that faults can be occurred in data bits and protocol links except LinkError link. A fault in protocol links except ParityError, is detected with the aid of two timers: TMRDAV is held by any input link and waits for DataAvailable signal; TMRTready is held by any output port and waits for ready signal. It is the job of GMU to find out which protocol link is faulty. In the designed switch element, routing and arbitrating between conflicting requests is done by using a bit-pattern associative router for each output link. The major advantage of using this router is the flexibility of changing priorities of requests incoming from input links.
Benzer Tezler
- Tanker şamandıra bağlama sistemlerinin yapay sinir ağları tekniğiyle optimizasyonu
Optimization of spread mooring systems with artificial neural networks
MURAT YETKİN
Yüksek Lisans
Türkçe
2014
Denizcilikİstanbul Teknik ÜniversitesiGemi ve Deniz Teknoloji Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. AYHAN MENTEŞ
- Finite element modeling of an origami inspired delta mechanism
Origamiden esinlenilmiş delta mekanizmasının sonlu eleman modellemesi
ATA ARJOMANDI FARD
Yüksek Lisans
İngilizce
2023
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. ATAKAN ALTINKAYNAK
DR. MERVE ACER KALAFAT
- Koordinat dönüşümüne dayalı zamanla değişen kayma yüzeyi tasarım yöntemleri
Coordinate transformation based time-varying sliding surface design methods
SEZAİ TOKAT
Doktora
Türkçe
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM EKSİN
- Kesir dereceli diferansiyelin doğrusal olmayan denetim yöntemlerine ve sinyal işleme tekniklerine uygulanması
Utilization of fractional order differentiation in nonlinear control methods and signal processing techniques
GÜRKAN KAVURAN
Doktora
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİnönü ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CELALEDDİN YEROĞLU
- Dalgacık dönüşümü tekniği kullanılarak akım serilerinin modellenmesi
Modeling of streamflow series using wavelet transform technique
MURAT KÜÇÜK
Doktora
Türkçe
2004
İnşaat Mühendisliğiİstanbul Teknik ÜniversitesiSu Ürünleri Mühendisliği Ana Bilim Dalı
PROF. DR. NECATİ AĞIRALİOĞLU