6502 optimizasyon sorusu

[i_r_on]

Saat frekansı 6502'nin 1mhz hızından çok daha yüksek bir micro işlemci (ona XMicro diyelim) sizin elinizdeki 6502'yi kontrol ediyor.
Programınız 6502'ye bağlı eprom üstünde $FF00-$FFFF aralığını kullanacak. Aynı zamanda bu 6502'ye 64k da ram bağlı.

XMicro ile 6502 arasındaki bağlantı sadece NMI / IRQ ve SO (Set overflow) bacakları üzerinden. XMicro'nun adres bus'ına yahut data bus'ına erişimi yok.

Ön bilgi :
- 6502 işlemcisi üzerindeki SO pin'i logic 1'den 0'a çekildiğinde 6502 status register'ı üzerindeki oVerflow flag'i set oluyor. Kenar tetiklemeli olarak çalışıyor. Örn. 1541 sürücüsünden haber almak için 6502 ile yazılabilecek en hızlı test rutininde kullanılabiliyor. (Loop : BVC Loop şeklinde)
- IRQ hattı bu hatta logic 0 verilmesi durumunda seviye tetiklemeli olarak çalışıyor. Yani 0 verildiği sürece interrupt oluşuyor.
- NMI ise kenar tetiklemeli çalışıyor yani bu hattaki sinyalin lojik 1'den 0'a çekildiği an bir kez tetikleniyor.

Evet soru şu : Sizden XMicro'yu kullanarak 6502'nin bağlı olduğu hafızaya yüklenme ve çalışma adresi değişken bir programı aktarmanız ve çalıştırmanız bekleniyor. Burada 6502 tamamen slave yani XMicro'ya herhangi bir şey dönemiyor. 6502 için max. 256 byte'lık* nasıl bir program yazarsınız? Yazdığınız program hangi hızda bu veri transferini yapar?

Şartları ekler ile tekrar edelim,

1. XMicro 6502'nin NMI, IRQ ve SO bacaklarını kontrol ediyor. İlaveten istediği zaman 6502'yi resetleyebiliyor.
2. 6502'ye bağlı CIA vesaire gibi ek bir peripheral çip yok, sadece RAM ve EPROM var.**
3. Kodunuz 6502 açıldığında $FF00-$FFFF aralığında çalışmaya hazır olacak. Yüklenecek program bu aralığa ve zero page'e denk gelmiyor. Bellek kullanımında herhangi bir kısıt yok.
4. Siz 6502 tarafında hızlıca handle edebildiğiniz sürece XMicro üstünde yeterince hızlı interrupt üretebiliyorsunuz.

Soru aslında kendi yazdığım bir kod ile ilgili optimizasyon sorusu olacaktı. Belki tamamen farklı bir anlayışla probleme yaklaşan çıkar diye formatını değiştirdim.

* : Aslında daha az. Interrupt vektörleri de aynı adres bloğunda olduğu için. 256 byte 6502 için gani gani program hafızası demek gerçi.
** : Başka yan birim yoksa çalıştırılan program ne işe yarayacak diye düşünebilirsiniz. Doğru bir düşünce ancak problemin tanımı gereği olmadığını varsayıyoruz. Pek tabii aktarılan programla faydalı bir şeyler yapılabilir.

[wizofwor]

Koskoca Commodore benden daha iyisini düşünmüştür diyerek jump table kullanırdım.

-Bunun için 256 byte hafıza içinde önceden belirlenmiş iki baytı NMI vektör adresi olarak ayırmam gerekecek.
-Rom'da NMI oluştuğunda 6502'nin NMI vektöründe belirtilen adrese atlayacağı bir IRQ rutini olacak.

Programı belleğe nasıl kopyalacağını ise anlamadım. Datayı SO bacağını üzerinden mi göndermeyi planlıyorsun? Biraz düşününce 6502'nin iki modu olması lazım. Yükleme ve çalıştırma. Pratik bir kullanım için çalışma modundayken yükleme moduna alabilmemiz gerekir (Arduino bootloader'da olduğu gibi).

Bu durumda ROM'da üç ayrı rutinim olurdu.
NMI rutini: NMI oluştuğunda yükleme rutinini çalıştıracak
çalışma rutini: Jump table'dan programın başlangıç adresine atlayarak programı çalıştıracak.
yükleme rutini: SO ve IRQ bacakları üzerinden veri alışverişi yapacak. Yükleme bitince çalışma rutinini çağıracak.

[i_r_on]

6502'de malesef iki değişik mod yok. Bootloader tadinda bir calisma mantigi yok. Ilaveten avr/pic gibi mikrolarda bulunan zamanlayici, uart veya dogrudan pin gpio gibi ozellikler de yok.

Soru aslinda hiz optimizasyonu sorusu. 256 byte kisiti esnetilebilir.

Transfer icin So/irq/nmi icinden istenen kombinasyon kullanilabilir. Teoride ve pratikte bu mumkun.

[wizofwor]

6502'de malesef iki değişik mod yok. Bootloader tadinda bir calisma mantigi yok.

Arduino bootloader örneğini verirken bu şekilde çalışan iki ayrı modu bizim kodlayacağımızı düşünmüştüm. İlgili rutinler rom'a yazılarak rahatlıkla yapılabilir.

Arduino bu işi sürekli olarak seri portu kontrol ederek yapıyor. Sen benzer bir işi NMI veya IRQ kullanarak yapabilirsin.

[i_r_on]

Dogrudur islem olarak yaptigimiz is bootloading.

Benim halihazirda calisan bir cozumum var bu arada. Maksat daha hizlisi yapilabilir miyi sorgulamak.  Kendi cozumumu yazip sartlandirmak istemedim kimseyi.

[wizofwor]

Halihazırda çalışan bir sistemin hızını sorgulayacak nerede dar boğaz oluştuğunu tespit etmek lazım. Madem şimdilik kendi sisteminden bahsetmemeyi tercih ediyorsun. Önce diğer arkadaşların fikirleri de aşağıya gelsin. Daha sonra senin sistemi tekrar soracağım. Zira psid projen hakkında merak ettiğim çok detay var.

[nightlord]

bu problem coook degisik sekillerde cozulebilir. su an cok uzun yazamayacagim ama kisaca aklimdakileri bosaltayim masaya:

- buradaki ana olay protokolun tanimlanmasi: bu tanimlamayi da ben baslangic durumu ve usecase'ler uzerinden yaparim. Burada yazilanlardan benim anladigim su:
  - boot edildiginden 6502 dinleme moduna geciyor. Komutlar geldiginde bu komutlarda soylenen seyi senkron/bloklayarak yapiyor. komutu bitirdiginde tekrar dinleme moduna donuyor. Komutlar sadece tek yonde (micro'dan 6502''ye dogru) akabiliyor
  - 2 komuttan bahsettik: mem copy ve execute

- bu protokol tanimi dogru degilse yanlis anlamisim, i_r_on sen beni duzelt

- bu noktada iki level var bu protokol icin:
  - low level: byte dizisi gonderme
  - high level: komut isleme

- byte dizisi gonderme: bunun icin robustness falan acisindan nasil kriterlerin var ona bakmak lazim. Keza genelde kopyalanan data miktari ne kadar. Kilobaytlar mi, 3-5 bayt mi? Bazi varsayimlar yapayim: genelde faydali dise gelir data miktarlarinin kilobayt mertebesinde olacagini varsayiyorum. enim aklima gelen en basit ve nispeten hizli yol su olur (obur micronun cok daha hizli oldugunu ve exact timing ile bayt gonderebildigini varsayarak):
- nmi ile bayt serisi baslangici
- nmi handler icinde rol rol rol rol rol rol rol rol sta inx bne
  - bu noktada bir dizayn karari daha aliyorum: memcopy = block copy. yani bir seferde 256 bayt gondericem.
  - micro timing'i yukaridaki komutlarin cycle'larindan cikariyor. yani mesela 1Mhz 6502 icin protokol yaklasik nmi, sonra 7us wait, sonra 8 bit her biri 2 us. sonra 10us wait between bytes. bastaki 7ms wait disinda gerisi 256 kere tekrar. 256 bayt icin toplam transfer suresi 7 + 256 * ( 8 * 2 + 10) ~ 6.7 msec.
  - ilk blok icinde bu transferde toplam kac blok gelecegi, bellekde nereden baslayarak kopyalanacagi gibi metadatalar olur.
  - blok basina 1 nmi

- dedigim gibi burada kullanim paterninin genelde 15-20 blokluk program gonder sonra onu calistir oldugunu varsayiyorum. yani ne biliyim mesela 4K'lik bir program 17 transferde calistirilabilir ( ~ 120 msec).

programin ana loopunda hi-level protokol durumunu takip ederdim. aklima 2 durum geliyor: Idle, Transfering. Basta idle durumdayiz, ilk nmi handler'da  256 bayt kopyalandiktan sonra handler bizi transfer state'ine aliyor bir de flag'i set ediyor. ana dongu bu flag'de bloklanmis. flag set edilince devam ediyor (bu bir blok data geldi demek) gelen bloga bakip nmi icindeki sta komutunun adresini target'a set ediyor falan.

- dusundukce aklima baska optimizasyonlar geliyor. iki ayri nmi handler rutini yapilir. biri ilk paket icin. 3 baytlik bir paket open looplar ile alir. 1. byte blok sayisi. 2.3. baytlar baslangic adresi. bunu kullanarak ikinci nmi handler icindeki sta hazirlanir (ikinci nmi handler yukarida anlattigim bir seferde 256 bayt alan)
- 1. nmi handler ayni zamanda exec komutu da calistirabilir. mesela blok sayisi 0 ise bu exec anlamina gelsin diye tanimlayabiliriz.

Ozetlersek:
- NMI handler 1: 3 bayt al. birinci bayt 0 ise 2.3. baytlari mainloop'ta bir yere kopyala ve rti. birinci byte 0 degilse 2. handler'i hazirla (icindeki sta'yi 2.3. baytlardan set et. blok sayisini set et, NMI vectorunu 2. handler'a set et (bi dahaki nmi da ona atlayacagiz ve rti
- NMI handler 2: 256 bayt al. ve direk bellege kopyala. bu is bittikten sonra blok sayacini artir, sta'nin hi byte'ini artir. beklenen blok sayisini kontrol et olmadiysa rti. olduysa nmi vectorunu handler 1'e cevir, blok sayacini sifirla, rti.
- ana dongu:
block:
    jmp block
target:
    jsr $1234

    lda #$4c
    sta block ; make the command jmp again to block
    jmp block

nmi handler 1, exec komutu geldiginde lda #$a9 sta block. ile ana donguyu unblock ediyor. baslangic adresini de target +1 ve target +2 adreslerine yaziyor.

micro tarafindan 3 baytlik komut paketleri veya 256 baytlik data paketleri gonderilebiliyor. hatta bu sistem bir once gonderilmis bir kod blogunu execute ederken yeni komutlar ve paketler bile alabilir.(execute edilen kod interruptlari kurcalamiyorsa

sanirim bu kod  256 byte icine de rahat rahat sigar. nmi handler 1 $60 bayt'tan az tutar nmi handler 2 de $40 $50 bayt tutar. main loop da gordugunuz gibi $10 bayt falan.

irq'yu kullanmadim. sistem nmi arti so kullaniyor

[i_r_on]

@nightlord : SO pin'ini tam olarak nasıl kullanacağını açıklamamışsın. 256 byte için 6.7 msec bana fazla iyimser geldi SO pin'i üstünden overflow flag'i set edilince clear etmesi 6502'ye kalıyor. Zamanlamanın da iyi tutturulması lazım, clear edeyim derken micro o anda set edebilir.  6502'deki en hızlı komutlardan bir kaçını çağırsan bile en az 6-10 cycle yersin, bu da bit başına en az 6-10 microsecond'a gelir. NMI'ı bulk transfer için kullanmadığından interrupt'a girmek ve dönmek için gerekli 7+6=13 cycle'ı saymayabiliriz.

Belirli bir kilobyte sınırı yok aslında, varsayımın doğru. İşe yarar bir şeyler için en az 1 kaç kb'lik transfer söz konusu. Pek tabii çok daha büyük programlar da aktarılabilir. Tek aktarım yöntemi bu olacağı için düşük miktarlarda veri için optimizasyona gerek yok.

Okurken kaçırmış olabilirim (hızlıca yazıyorum, detaylı okuyacağım), programın transfer edileceği bellek bölgesini micro belirliyor. Daha baştan transferi o bölgeye yapmak gerekiyor. Pek tabii transfer sonrası relocate etmek de bir seçenek olabilir.

ps: Bu arada benim durumumda senkronizasyonu sağlamak bu kadar kolay değil ama bu çözümü de ortaya koymak lazım. Özellikle zaten bu konuda da varsayımda bulunmadım cevaplar kısıtlanmasın diye. Micro'nun her zaman senkron olamadığı durumda kompleks de olsa error checking vesaire ile hızlı transfere yine devam edilebilir.

[nightlord]

Pardon problem benim so pininin kenar tetiklemeli oldugunu kacirmamdan kaynaklaniyor. Ben o pininin durumunun direk overflow flag ile mirror edildigini sanmistim. Oyle olsaydi, her role komutu ile bir bit alabilirdik. gonlumden tek bit bile olsa arada memory mapped bir buffer olsa diye geciyor  

[i_r_on]

Bu arada iyi okumamışım, interrupt başlangıcı 7 cycle hesaba dahil edilmiş.

Sorular ve notlar

1. Overflow flag'den a register'ına ana rutinde nasıl transfer yapılıyor? (Biraz daha dikkatli okuyunca anlıyorum ki benim overflow dememden sen carry anladın.)

2. NMI handler'da RTI neden yok?

3. O anda çalışan bir komut varsa bu komut bitmeden interrupt tetiklenmiyor, buraya da en az bir 3 cycle buffer lazım.


Aslında kritik soru SO'yu nasıl kullandığın. Gördüğüm bir örnekte vatandaş bit başına 60 cycle harcamıştı. Hani bu rakamdan daha iyi bir rakama ulaşılabilir pek tabii ancak bir bit için 8-10 cycle gerçekten imkansız.

ps: Bahsettiğim örneğe daha dikkatli baktım yanlış görmüşüm bit başına harcadığı zamanı. Bit başına 36 cycle, byte başına da ekstra 37 cycle harcıyormuş. Gayet iyi rakamlar, hız açısından benim çözümümden biraz iyi

[i_r_on]

Cevabımı senin cevabını görmeden önce yazmıştım. Bu arada muhtemelen farkındasındır ya da olacaksındır. Bir sıkıntı daha var, interrupt handler otomatik olarak statü register'ını stack'e bastığı için overflow flag nerede (ana program yahut int handler) set oluyorsa orada clear olmalı ya da int handler stack ile iştigal etmeli. Yoksa int handler bittiğinde overflow flag eski hali ile stack'ten çekiliyor.


@wizofwor
Bu arada psid player mevzunda istediğini sorabilirsin. Seve seve cevaplarım. Retrojen işyerinde bloklu olduğu için, telefondan da yazmak zor olduğu için böyle bazen okunan şeye sonradan cevap yazınca aslında okuduğunun tamamına cevap vermediğini anlıyor insan

Retrojen admin'e not, websense'de bloklusunuz bir el atın Games kategorisinde gözüküyor site.

[nightlord]

diger sorularina gecmeden SO ve overflow flag konusalim:
- evet ben ilk cevaplarda onu tamamen carry flag olarak dusunuyordum. o yuzden rol rol rol rol calisiyor (hatta edge detect bile ok cunku akumulatoru 0 ile ilklersek her rol hi-bit'i geri carry flag'e ittigi icin otomatik olarak silmis oluyoruz) ama bu yanlis cevap gecelim
- su an canim oyle istedigi icin 6502 tarafindaki transfer hizini maksimize etmeye bakiyorum bu daha hassas timing ve ihtimalen xmicro kodunun daha zor olmasi demek ama olsun maksat beyin egzersizi.
- simdilik aklima gelen en hizli bayt transfer rutinini yaziyorum. baya demoscene style optimizasyonlar

loop:
tsx ; save stack pointer
php
clv
php
clv
...
php
clv ; push status register to eight consecutive bytes in stack
txs ; restore stack pointer, we have captured 8 bytes somewhere in $100-$200 range lets call the first address stack,

ldx stack
lda tab0,x ; set bit 7 based on bit 6 of read value
ldx stack+1
ora tab1,x
ldx stack+2
ora tab2,x
...
ldx stack+7
ora tab7,x ; byte now in accumulator

sta dest, y
iny
bne loop

13 cycles per bit + 14 cycles per byte = 118 cycles/byte

trikler:
- overflow flag'i stack'e atmak (komple status register ile beraber). sonucta 8 byte oluyor stackte, bunlarin 6. bitlerini birlestirerek istedigimiz byte'i elde edicez.
- bu 6. bitleri birlestirme isini hizli yapmak icin $800 bayt look up table'lara yakiyoruz. her tablo 6. bit'in degerini hedef bite yazmaya yariyor. mesela 0. bit icin kullandigimiz tablo 256 degere sahip 6. bitin 0 oldugu butun indexler icin deger 0. 6. bitin 1 oldugu indexler icin deger 1. yani tabloda 0 - 63 arasi  ve 128 - 191 arasi 0 digerleri 1. ayni sey diger 7 tablo icin de gecerli. tek fark 1 olan degerler diger tablolarda 1 yerine ilgili bite shift olmus hali: tab1 icin 2, tab2 icin 4, tab3 icin 8 vs.
- her ldx, sta/ora cifti ile bir biti alip akumulatorde dogru bite yerlestiriyoruz.
sonucu y index ile 256 adrese yaziyoruz.
- protokolun so pininde gorunen hali soyle oluyor: basta biraz don't care. sonra 8 tane 5 cycle'lik slot sonra ~70 cycle falan bosluk (ldx, ora ciftleri + loop)
- ve dedigim gibi xmicro'nun cycle-exact zamanlama ile so pin ustundeki transition'lari yapabildigini varsayiyorum

[i_r_on]

Evet bu yöntem iş yapar. Tabii her seferinde XMicro'nun SO pin'ini high'a getirmesinin CLV ile PHP arasına denk gelmesi lazım.
Datasheet der ki
"Set Overflow Flag (S.O.)
A NEGATIVE going edge on this input sets the overflow bit in the Status Code Register. This signal is sampled on the trailing edge of PHI1."

Bunda da sıkıntı yok. İmkansız değil, 16mhz bir avr ile kolayca yapılabilir. Ancak her 8 bit transferinden sonra araya senkronu tutturmak için overflow'u bekleyen loop atmak lazım. Bir defa dönse 3 cycle da buradan gider.

Tabii pratikte deneyip gerçek hızını görmek lazım (hani araya parça koymak gerekiyor mu diye). 800 byte lookup table'a bir şekilde transfer edilen dataya göre relocate edilerek yer açılabilir.

Bu arada kendi rutinimde yeterince optimizasyon yapmadığım hissi uyandı Gerçi ben biraz temiz olsun başım ağrımasın tadında yazdım. Senkron transferden başta vazgeçtim çünkü zamanlamayı tutturmam çok zor. Veriler sd karttan okunup bir yandan da display sürülüyor. (Verileri cache'leyecek yeterince bellek yok. Gerçi 64 byte'lık falan burst'ler şeklinde yapılabilir. O kadar yer açabilirim.)

[nightlord]

Tabii her seferinde XMicro'nun SO pin'ini high'a getirmesinin CLV ile PHP arasına denk gelmesi lazım.

o kadar dar degil aralik aslinda. clv'nin son cycle'i ile php'nin son cycle arasina gelmesi lazim. cunku iki komuttada status registerine bakilan cycle son cycle'lar. yani xmicronun 3 cycle'lik bir penceresi var

Ancak her 8 bit transferinden sonra araya senkronu tutturmak için overflow'u bekleyen loop atmak lazım. Bir defa dönse 3 cycle da buradan gider.

Burada ne demek istedigini anlamadim. 6502 tarafinda hicbirsey beklemiyoruz. Sekizinci biti gonderdikten sonra exactly 78 cycle bekleyip bir sonraki byte'i almaya basliyoruz. Baska degisle protokol tam 118 cycle'lik periyodlarla bayt gonderiyor. 8 x 5 = 40 cycle icinde 8 bit + 78 cycle don't care. Bunu 256 kere tekrarliyoruz bir nma'da

Tabii pratikte deneyip gerçek hızını görmek lazım (hani araya parça koymak gerekiyor mu diye). 800 byte lookup table'a bir şekilde transfer edilen dataya göre relocate edilerek yer açılabilir.

relocate etmek bence gereksiz bir komplikasyon olur. o zaman interrupt handlerdaki lda tabN,x satirlarini da degistirmek gerekir. onun yerine 64K adres alaninda bir $800 secip bu ise adamak daha kolay geliyor bana.

Gerçi ben biraz temiz olsun başım ağrımasın tadında yazdım. Senkron transferden başta vazgeçtim çünkü zamanlamayı tutturmam çok zor. Veriler sd karttan okunup bir yandan da display sürülüyor. (Verileri cache'leyecek yeterince bellek yok. Gerçi 64 byte'lık falan burst'ler şeklinde yapılabilir. O kadar yer açabilirim.)

atalarimiz ne demis: "premature optimization is the root of all evil".

ama bit basina handshake yapmak performansi order of magnitude kotulestirecek (turkcesi buyukluk kertesi imis simdi ogrendim). dedigin gibi bayt gruplari kazanc saglayabilir. hatta bu kod kac bayt gonderdigine cok da bagli degil (sadece nmi+rti overhead). bir seferde bir bayt bile gondersen olur(118 cycle yaninda 13 cycle goz ardi edilebilir oldugu icin). yeter ki bit basina handshake durumuna dusme

[i_r_on]

Ancak her 8 bit transferinden sonra araya senkronu tutturmak için overflow'u bekleyen loop atmak lazım. Bir defa dönse 3 cycle da buradan gider.

Burada ne demek istedigini anlamadim. 6502 tarafinda hicbirsey beklemiyoruz. Sekizinci biti gonderdikten sonra exactly 78 cycle bekleyip bir sonraki byte'i almaya basliyoruz. Baska degisle protokol tam 118 cycle'lik periyodlarla bayt gonderiyor. 8 x 5 = 40 cycle icinde 8 bit + 78 cycle don't care. Bunu 256 kere tekrarliyoruz bir nma'da

Yazdıklarında NMI değil de önde çalışan programda transferi yaptığını düşündüm. Her 8 bitte bir senkronizasyon iki tarafın saatlerini eşitlemek için. Ki burada NMI kullanmaya bence gerek yok, olay tamamen SO pin'i üstünden koordine edilebilir. Her iki tarafta da clock sinyali net beklenen değerde olmayacaktır çünkü. Senkron çözüme gitmişken NMI'ın overhead'ine de bence gerek yok.

Tabii pratikte deneyip gerçek hızını görmek lazım (hani araya parça koymak gerekiyor mu diye). 800 byte lookup table'a bir şekilde transfer edilen dataya göre relocate edilerek yer açılabilir.

relocate etmek bence gereksiz bir komplikasyon olur. o zaman interrupt handlerdaki lda tabN,x satirlarini da degistirmek gerekir. onun yerine 64K adres alaninda bir $800 secip bu ise adamak daha kolay geliyor bana.

Uygulamaya göre karar alınabilir. Benim case'imde sid transfer edip bunları çalıyorum. Ne execute ettiğim kodun ne de kullandığım ram'in sid'in yüklendiği adreslerle overlap etmemesi lazım. Gerçi benim örneğim için de $D000-$E000 arasındaki IO bölgesinden sid'lerin kullanmadığı bir bölge seçilebilir.

atalarimiz ne demis: "premature optimization is the root of all evil".

ama bit basina handshake yapmak performansi order of magnitude kotulestirecek (turkcesi buyukluk kertesi imis simdi ogrendim). dedigin gibi bayt gruplari kazanc saglayabilir. hatta bu kod kac bayt gonderdigine cok da bagli degil (sadece nmi+rti overhead). bir seferde bir bayt bile gondersen olur(118 cycle yaninda 13 cycle goz ardi edilebilir oldugu icin). yeter ki bit basina handshake durumuna dusme

Aslında ben neredeyse hiç optimizasyon yapmadım (kodu yazdıktan sonra). Pek tabii 2 misli, 3 misli - 10 misli kazanç sağlamıyorsam optimizasyon yapmanın bir anlamı yok.  Bakayım demo sahnesinin üç kağıtları yöntemimi değiştirmeden bit başına 55 cycle'dan beni nereye götürecek. Optimize ettikten sonra ben de kodumu paylaşırım.

Stack'ten tablo yardımıyla byte'ı oluşturma yöntemi güzelmiş bu arada. Bu doğaçlama mı gelişti yoksa daha önce bir yerde benzeri kullanılmış mıydı?

ps: Ben kaçtım, cevapları artık sabah okurum. Paylaşım için teşekkürler