A new algorithm for reordering buffer management problem and experimental evaluations in discrete distributions
Arabellek ile yeniden sıralama problemi için yeni bir algoritma ve ayrık dağılımlarda yapılan deneylerin sonuçları
- Tez No: 676172
- Danışmanlar: PROF. DR. MUHAMMED OĞUZHAN KÜLEKCİ
- 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: 2021
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
- Sayfa Sayısı: 91
Özet
Yeniden sıralama problemleri ekonomiden bilgisayar sistemlerine kadar geniş bir yelpazede doğal olarak ortaya çıkar ve önemli bir rol oynar. Yeniden sıralama probleminde, görevler ya da işlemler bazı öncelik kısıtlamaları dikkate alınarak belirli bir kaynağa atanmaktadır. Görevlerin belli bir süreliğine geciktirilebildiği bazı uygulamalarda arabellekler önemli bir rol oynar. Arabellekler, bazı görevleri geçici olarak depolayarak, görevlerin kaynağa girişine öncelik kısıtlamaları lehine izin vermek içi kullanılabilir. Bu nedenle, arabellek yönetimi yeniden sıralama problemlerinde belirleyici bir role sahiptir. Sabit disklerde, dönen yüzeyin üzerinde bir okuma/yazma kafası mevcuttur ve bu kafanın konumu disk içerisinde hangi silindire erişilebileceğini belirler. Kafanın silindir üzerindeki hareketi zaman alır ve bu zaman sabit diskin performansını belirler. Erişimlerin hedef silindirlerin pozisyonuna göre yeniden sıralanması için arabellek kullanılması, erişim zamanını azaltabilir. Bilgisayar grafiklerinde görselleştirme yapılırken çizim temel öğeleri kullanılır. Görselleştirme sisteminin performansı, çizim temel öğelerinde gerçekleşen durum değişiklerine bağlıdır. Durum değişiklikleri iki ardışık temel çizim öğesi arasında doku, renk veya gölge farklılıkları olduğunda meydana gelir. Görselleştirme sırasında karşılaşılan durum değişikleri sistemde gecikme yaratır, bu nedenle benzer özniteliklere sahip temel çizim öğelerinin arka arkaya işleme alınması sistem için faydalı olacaktır. Arabellek gelen temel çizim öğelerini özniteliklerine göre yeniden sıralamak için kullanılabilir. Ağ iletişim sistemlerinde, iki ardışık paketin farklı düğümlere gönderilmesi bir maliyet oluşturur. Bu nedenle sunucunun aynı düğüme gönderilecek paketleri bir arada göndermesi sitem için faydalıdır. Arabellek paketlerin uygun şekilde yeniden sıralanması için kullanılabilir. Otomotiv endüstrisindeki boyama atölyelerinde, otomobil gövdeleri, her otomobil gövdesinin kendi son kat boyası ile boyandığı bir son kat boyamadan geçmektedir. Birbirini izleyen iki arabanın farklı renklerde boyanması gerekiyorsa, renk değişikliği gerekir, bu da bir temizlik ve kurulum maliyetine neden olur. Bu maliyet arabellek kullanılarak yapılan bir yeniden sıralama ile azaltılabilir. Arabellek ile yeniden sıralama probleminde, belirli bir öznitelikle karakterize edilen n öğeden oluşan bir girdi dizi bulunmaktadır. Anlatımı sadeleştirmek adına bu özelliği öğenin rengi olarak adlandıracağız. Girdi dizisindeki tüm öğeler bir servis istasyonu tarafından işlenmek üzere sırada beklemektedir. Öğelere renklerine göre servis istasyonu tarafından farklı işlemler uygulanacaktır. Uygulanacak işleme göre servis istasyonundaki sürecin değiştirilmesi maliyet oluşturmaktadır. Dolayısıyla, farklı renklere sahip her bir ardışık öge çifti için bir maliyet oluşur. Maliyeti en aza indirmek için içerisinde k öge barındırabilen bir arabelleğe sahibiz. Sırada bekleyen öğeler önce arabelleğe giriş yapar. Arabellek dolduğunda, arabellek ile yeniden sıralama algoritması bir çıktı rengi seçer ve arabellekte bu renge sahip olan tüm öğeler servis istasyonuna iletilir. Öğeler servis istasyonu tarafından işlendikten sonra çıktı dizisine eklenir. Arabellekteki boş pozisyonlar sırada bekleyen öğelerle tekrar doldurulur. Bu mekanizma girdi dizisindeki tüm öğeler işlenene kadar devam eder. Tüm algoritmalar boş bir arabellekle başlar ve biter. Arabellekte son seçilmiş çıktı rengine sahip bir öge varsa algoritma kararında bir değişiklik yapmaz. Ayrıca, arabellekte boş bir pozisyon varsa, algoritma arabellekten herhangi bir öğeyi servis istasyonuna iletmez. Arabellek ile yeniden sıralama problem, problemin bileşenlerine göre sınıflandırılabilir. Problemin tanımlayıcı özelliklerinden birisi maliyet fonksiyonudur. Maliyetin tek tip olduğu durumda, herhangi bir renkten diğerine geçerken aynı maliyet oluşur. Bu nedenle maliyet çıktı dizisindeki öznitelik değişikliklerinin sayısı olarak ölçülebilir. Maliyetin tek tip olmadığı durumda ise, bir renkten diğerine geçerken farklı maliyetler ortaya çıkabilir. Problemin çevrimiçi varyantında, algoritma gelecekte arabelleğe ulaşacak öğeler hakkında bilgi sahibi değildir. Diğer bir deyişle, girdi dizisi önceden bilinmemektedir ve algoritma yalnızca arabellekte bulunan öğeleri dikkate alarak karar vermek zorundadır. Öte yandan problemin çevrimdışı varyantında, algoritma girdi dizisini tamamını dikkate alarak karar verebilir. Problemin maksimizasyon varyantında, amaç çıktı dizisindeki öznitelik değişliklerini en aza indirmek yerine, girdi dizisinde elenen maliyet sayısını en üst düzeye çıkarmak olarak tanımlanmıştır. Bu tez çalışmasında, arabellek ile yeniden sıralama probleminin çevrimdışı varyantında ideal çözüm için gerekli olan en az tampon büyüklüğünü kanıtladık. Renk seçiminin her zaman arabellek dolu olduğunda yapıldığı ve algoritmanın arabellekte en çok bulunan rengi çıktı rengi olarak seçtiği varsayımıyla, o_1
Özet (Çeviri)
Scheduling problems emerge naturally in a broad range of application areas from economics to computer systems. In the scheduling problem, tasks or activities must be assigned to a given resource while satisfying some precedence constraints. For some applications in which tasks can be ignored for a period of time, buffers can be used to store the delayed items temporarily to permute the input of tasks. In these applications, buffer management strategies play an important role. In the reordering buffer management problem, we have an input sequence of n items which are characterized by a particular attribute, which we will refer to as color, and a buffer of size k. A cost occurs when serving a pair of consecutive items with different colors. A reordering buffer management algorithm aims to permute the input sequence using the buffer to minimize the total cost. In this thesis, we proved the minimum buffer length for the optimal solution to the reordering buffer management problem in the offline setting. With the assumption that color selection is always made when the buffer is full, selecting the most frequent color from buffer given the smallest buffer size k that satisfies either o_1
Benzer Tezler
- Leon3 mikroişlemcisi tabanlı sistem tasarımı
Leon3 microprocessor based system design
AHMET ÇAĞRI BAĞBABA
Yüksek Lisans
Türkçe
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. SIDDIKA BERNA ÖRS YALÇIN
- Üç boyutlu canlandırma sisteminde gerçeğe benzetme
Başlık çevirisi yok
HÜNKAR ÜNVERDİ
Yüksek Lisans
Türkçe
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN TUNALI
- Algoritma animasyonu sistemleri konusunda inceleme
Başlık çevirisi yok
NAZAN ÇAYRAK
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. TAKUHİ NADİA ERDOĞAN
- Evrensel aydınlatmada kullanılan foton haritalama yönteminin paralelleştirilmesi
Parallelization of photon mapping technique used in global illumination
YUSUF YAVUZ
Yüksek Lisans
Türkçe
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAnkara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SÜLEYMAN TOSUN
- Pararllel rendering algorithms for distributed-memory multicomputers
Çok işlemcili dağıtık hafızalı bilgisayarlarda paralel görüntüleme algoritmaları
TAHSİN MERTEFE KURÇ
Doktora
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT