Mavzu: Tashqi xotira uchun ma’lumotlar tarkibi va algoritmlari Bajardi

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI

VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Mustaqil ish

Mavzu: Tashqi xotira uchun ma’lumotlar tarkibi va algoritmlari

Bajardi:423-17 guruh talabasi

Uzaqov Furqat

Tekshirdi: Yusupova Z

Toshkent 2020

Reja:

1.Tashqi xotira algoritmlari.

2.Tashqi xotira modeli.

3.Parallel tashqi xotira.

1.Tashqi xotira algoritmlari.

Hisoblashda, tashqi xotira algoritmlari yoki yadrodan tashqaridagi algoritmlar bir vaqtning o'zida kompyuterning asosiy xotirasiga sig‘maydigan darajada katta bo'lgan ma'lumotlarni qayta ishlashga mo'ljallangan algoritmlardir. Bunday algoritmlar qattiq disklar yoki lenta drayvlar singari sekin xotira (yordamchi xotira) da saqlanadigan ma'lumotlarni yoki xotira kompyuter tarmog'ida bo'lganda ma'lumotlarni samarali olish va ularga kirish uchun optimallashtirilgan bo'lishi kerak, tashqi xotira algoritmlari tashqi xotira modelida tahlil qilinadi.

2.Tashqi xotira modeli.

Tashqi xotira algoritmlari tashqi xotira modeli (yoki kiritish-chiqarish modeli yoki diskka kirish modeli) deb nomlangan hisoblashning idealizatsiya qilingan modelida tahlil qilinadi. Tashqi xotira modeli bu RAM mashinasi modeliga o'xshash mavhum mashina, lekin asosiy xotiradan tashqari kesh bilan ta'minlangan. Model o'qish va yozish operatsiyalari keshda asosiy xotiraga qaraganda ancha tezroq bo'lishini va uzoq tutash bloklarni o'qish disk o'qish va yozish boshi yordamida tasodifiy o'qishdan tezroq bo'lishini aks ettiradi. Algoritmning tashqi xotira modelidagi ishlash vaqti talab qilinadigan o'qish va yozish soni bilan belgilanadi.Model Alok Aggarval va Jefri Vitter tomonidan 1988 yilda kiritilgan, tashqi xotira modeli keshni unutgan model bilan bog'liq, ammo tashqi xotira modelidagi algoritmlar blok hajmini ham, kesh hajmini ham bilishi mumkin. Shu sababli, model ba'zan keshdan xabardor model deb nomlanadi.

Model ichki xotirasi yoki cheksiz tashqi xotiraga ulangan M kattalikdagi protsessordan iborat. Ham ichki, ham tashqi xotira B hajmidagi bloklarga bo'linadi. Bitta kirish / chiqish yoki xotirani uzatish operatsiyasi B qo'shni elementlar blokini tashqi xotiradan ichki xotiraga ko'chirishdan iborat bo'lib, algoritmning ishlash muddati ushbu kirish / chiqish operatsiyalari.

Tashqi xotira modelidagi algoritmlar bitta ob'ektni tashqi xotiradan olish B hajmining butun blokini olishidan foydalanadi, bu xususiyat ba'zan mahalliylik deb ataladi.N-ob'ektlar orasida elementni qidirish tashqi dalil modelida B dallanuvchi omil B bo'lgan B-daraxt yordamida amalga oshiriladi. B-daraxt yordamida qidirish, qo'shish va o'chirishga o'z vaqtida O(log_BA)-da erishish mumkin (Big O yozuvida). Nazariy ma'lumot, bu ushbu operatsiyalar uchun eng kam ish vaqti, shuning uchun B daraxtidan foydalanish asimptotik jihatdan maqbuldir.

Tashqi tartiblash - bu tashqi xotira sozlamalarida saralash. Tashqi tartiblash, tezkor kortga o'xshash taqsimlash tartibida yoki M -way birlashish tartibida amalga oshirilishi mumkin. Ikkala variant ham N moslamalarni saralash uchun O(N/Blog_M/BN/B) ning asimptotik optimal ishlash vaqtiga erishadi. Ushbu chegara tashqi xotira modelidagi tezkor Furye konvertatsiyasiga ham tegishli.

Almashtirish muammosi - N elementlarni ma'lum bir almashtirishga almashtirish. Buni yoki saralash orqali amalga oshirish mumkin, buning uchun yuqoridagi saralash ish vaqti kerak, yoki har bir elementni tartibda qo'shib, joyning foydasiga e'tibor bermaslik kerak. Shunday qilib, almashtirish vaqtni amalga oshirishi mumkin.

Tashqi xotira modeli tasodifiy kirish mashinasi kabi ma'lumotlar tuzilmalarini tahlil qilishda foydalaniladigan boshqa keng tarqalgan modellarda modellashtirilmagan va ma'lumotlar tuzilmalari uchun pastki chegaralarni isbotlash uchun foydali bo'lgan xotira iyerarxiyasini ushlaydi. Model ichki xotiraga sig‘maydigan darajada katta hajmdagi ma’lumotlar to‘plamlarida ishlaydigan algoritmlarni tahlil qilish uchun ham foydalidir.

Odatda, bu to'liq ma'lumotlar to'plami bir necha gigabayt yoki hatto terabayt ma'lumotlardan oshib ketadigan geografik axborot tizimlari, ayniqsa raqamli balandlik modellari.

Ushbu metodologiya umumiy maqsadli protsessorlardan tashqari, GPU hisoblash va klassik raqamli signallarni qayta ishlashni ham o'z ichiga oladi. Grafikni qayta ishlash bloklarida (GPGPU) umumiy maqsadli hisoblashda, xotirasi kam bo'lgan kuchli grafik kartalar (GPU) (tez-tez RAM deb ataladigan tanish bo'lgan tizim xotirasi bilan taqqoslaganda) nisbatan sekin protsessordan foydalaniladi. GPU xotirasini uzatish (hisoblash kengligi bilan taqqoslaganda).

3.Parallel tashqi xotira.

Kompyuter fanida parallel tashqi xotira (PEM) modeli keshdan xabardor, tashqi xotiradan mavhum mashinadir.Bu bitta protsessorli tashqi xotira (EM) modeliga parallel hisoblash analogiyasi. Xuddi shu tarzda, bu parallel tasodifiy kirish mashinasiga (PRAM) o'xshash keshdan xabardor bo'lgan analogiya. PEM modeli o'zlarining shaxsiy keshlari va umumiy asosiy xotirasi bilan birgalikda bir qator protsessorlardan iborat.

Informatika sohasida maʼlumotlar tuzilmasi — samarali kirish va oʻzgartirishga imkon beradigan maʼlumotlarni tashkil qilish, managment va saqlash formati.Aniqrogʻi, maʼlumotlar tuzilmasi maʼlumotlar qiymatlari, ular orasidagi munosabatlar va maʼlumotlarga qoʻllanilishi mumkin boʻlgan funksiyalar yoki operatsiyalar toʻplami hisoblanadi.