niedziela, 25 kwietnia 2021

Laboratorium zaawansowanej elektroniki i automatyki 21

 Laboratorium zaawansowanej elektroniki i automatyki 21

 Układy analogowe i cyfrowe są coraz szybsze. Układy analogowe wymagają „czystego zasilania” same przy tym często generując silne zakłócenia. Rozwiązaniem jest zasilanie niskoimpedancyjne. Zasilanie mikrofalowego wzmacniacza mocy w smartfonie czy stacji bazowej musi być niskoimpedancyjne w bardzo szerokim zakresie częstotliwości bowiem zmiana napięcia zasilania wprowadza niechcianą modulacje i ogranicza moc maksymalną wzmacniacza RF przy chwilowo obniżonym napięciu co powoduje bardzo szkodliwą kompresje wzmacnianego sygnału.   

 Model każdego kondensatora ceramicznego i foliowego ( sensowne modele kondensatorów elektrolitycznych są skomplikowane ) ma równoważną szeregową z idealnym kondensatorem indukcyjność ESL i oporność ESR. Współcześnie najlepsze własności częstotliwościowe mają wielowarstwowe kondensatory ceramiczne MLCC w miniaturowych obudowach SMD – Multilayer Ceramic Capacitor szczególnie w wykonaniach z wieloma wyprowadzeniami o indukcyjności poniżej 0.1 nH jak na rysunku Muraty.


 Miniaturowy kondensator MLCC pojemności 1 nF ( oczywiście na małe napięcie ) ma rezonans szeregowy przy częstotliwości ca 300 MHz zaś przy pojemności 100 nF przy około 25 MHz. Kondensator pojemności 100 nF do montażu przewlekanego ma rezonans przy częstotliwości około 5 MHz więc różnica między nimi jest kolosalna.
Kondensatory w układzie łączone są z innymi elementami ścieżkami które też mają indukcyjność która musi być brana pod uwagę.
Jeśli równolegle połączymy „1” kondensator o większej pojemności z „2” o mniejszej pojemności to impedancja od lewej strony z uwzględnieniem indukcyjności krótkich ścieżek wygląda jak na wykresie. Oprócz rezonansów szeregowych kondensatorów lokalnie zmniejszających impedancje zasilania powstał też niestety szkodliwy rezonans z szeregowo połączonych pojemności, indukcyjności i rezystancji między nimi powiększający impedancje w pewnym zakresie częstotliwości. W każdym przypadku trzeba z planowanymi na PCB ścieżkami dobrać takie kondensatory aby uzyskać w „punkcie” odbioru zasilania jak najmniejszą impedancje w zakresie pracy ! Jeśli z lenistwa nie sprawdzimy szybko programem symulacyjnym impedancji zasilania czeka nas nieprzyjemna niespodzianka ! Warto brać pod uwagę rekomendacje producentów chipów. Impedancja ta ze specjalnymi  kondensatorami MLCC może być bardzo mała nawet przy częstotliwościach ponad 1 GHz.
Jeśli więc na schemacie pokazano kilka równolegle połączonych różnych kondensatorów ( lub tak jest w naturze na PCB ) to jest to efekt przeprowadzonej optymalizacji a nie widzimisię projektanta!
Na rysunku pokazano ideę szerokopasmowego niskoimpendancyjnego zasilania chipa. Najmniejszą pojemność ma sama struktura chipa (!) ale ta pojemność jest zarazem najbliżej poboru szybkozmiennego prądu w strukturze. W obudowie układu scalonego jest już kilka miniaturowych kondensatorów MLCC o większej pojemności. Na płycie  drukowanej jak najbliżej obudowy układu scalonego są kondensatory o takiej lub większej pojemności i wreszcie na wejściu samej płyty drukowanej jest para kondensatorów ( czasem mogą być 3 lub 4 ) o największej pojemności. Indukcyjność ścieżek z pojemnościami tworzy zarazem  dolnoprzepustowy filtr ( z zerami na częstotliwościach rezonansów szeregowych kondensatorów ) zakłóceń działający w obie strony !    

 Niskoimpedancyjne szerokopasmowe zasilanie jest potrzebne nie tylko do bardzo szybkich układów cyfrowych i analogowych jak powyżej ale także do zasilania inverterów mocy PWM jako że klucze mocy są coraz szybsze. Konstrukcja modułu trójfazowego mostka kluczy dla inwertera jest zoptymalizowana także pod kątem małej indukcyjności połączeń zasilania ( oraz połączeń kluczy ze sobą ) na której przy przełączaniu kluczy powstają szkodliwe szpilki napięć, które podwyższają wymagania napięciowe od kluczy co wprost przekłada się na koszt kluczy i spadek ich szybkości działania.
Pojemności kondensatorów ( implikują rezonans szeregowy kondensatorów i razem ze ścieżkami PCB funkcje impedancji ) wybrane są tak aby uzyskać jak najmniejszą impedancje w interesującym zakresie częstotliwości i przepięcia. W przypadku PWM oczywiście nie chodzi o częstotliwość modulacji ale o czasy przełączania prądów przez klucze!  
W UPS ( Uninterruptible Power Source  ) rodziny Smart wiodącej firmy APC zasilany z akumulatora jednofazowy mostek H ma po cztery połączone równolegle tranzystory Mosfet „8 mOhm/50V”. Za tym oznaczeniem mogą być typy Mosfetów od różnych producentów.
Zastosowano w zasilaniu mostka 6 miniaturowych kondensatorów foliowych pojemności 1 uF oraz dwa kondensatory elektrolityczne o bardzo małym ESR pojemności 2700 uF każdy.  Płyta drukowana jest dwustronna a kondensatory są rozmieszczone racjonalnie.
Na wykresie pokazano generacje energii przez PV w Polsce w kolejnych godzinach pierwszego kwartału 2021 roku. Moc zainstalowana wynosi już ponad 3 GW a produkcja przez kwartał wyniosłą zaledwie niepełne... 511 GWh !
Jesienią, zimą i wiosną generacja z PV jest niewielka ponieważ Polska na kuli Ziemskiej leży tam gdzie leży i tego w żaden sposób nie da się zmienić. W nocy, wczesnym ranem i późnym wieczorem oddawana do sieci generacja PV jest zerowa.

Monokrystaliczny Panel PV Q-Cells obrysu 1673 x 1030 mm ma typowe parametry nowoczesnych paneli. Przy testowym oświetleniu STC ( Standard Test Condition ) mocy 1000W/m2 o spectrum AM 1,5 według normy IEC 60904-3 najlepsze w grupie selekcyjnej panele  oddają moc 345W a najgorsze 325W.
Przy szeregowym połączeniu ogniw panelu szybki spadek sprawności wynika z technologicznej nieidentyczności ogniw.  Charakterystyczne jest to że prąd zwarcia wszystkich paneli jest prawie taki sam i takie same są napięcia jałowe natomiast napięcie pracy w punkcie MPP najlepszych pod względem sprawności paneli jest większe niż najsłabszych. W punkcie MPP prąd obciążenia jest tylko o circa 5% mniejszy niż prąd zwarcia !
Prąd zwarcia rośnie z temperaturą 0.045 /C a napięcie jałowe spada 0.27%/C a moc spada -0.35%/C co spowodowane jest też wzrostem rezystancji wewnętrznej.
Przy silnym słonecznym oświetleniu sprawność najlepszych PV przekracza 20% ale dla wszystkich sprawność maleje z oświetleniem ale przy oświetleniu 100W/m2 sprawność wynosi niezłe 93% nominalnej.
 Panele te wedle gwarancji mają się wyróżniać znakomitą trwałością. W ciągu pierwszego roku sprawność z początkowej relatywnych 100% ma spaść mniej niż o 2% a później mniej niż 0.5% rocznie i po dziesięciu latach ma przekroczyć 93.5% a po ćwierćwieczu 86% mocy znamionowej.

Amerykańskie laboratorium PVEL od 10 lat testuje panele PV sprzedawane przez 75 różnych producentów. Trwałość PV mocno zależy od technologii wykonania. Uszkodzenia „krzemu” są wywoływane przez silne naprężenia mechaniczne wynikające m.in. z uderzeń wiatru.  Podczas testów PVEL panele poddawane są trzykrotnie obciążeniu od ciśnienia 2400 Pa, odpowiadającemu ekstremalnie grubej pokrywie śnieżnej lub jednostajnemu działaniu wiatru o huraganowej sile. W każdym cyklu  ciśnienie oddziałuje z góry, a następnie z dołu przez godzinę. Druga część testu odbywa się pod niższym ciśnieniem (1000 Pa), ale obejmuje aż 1000 cykli.
Pękanie przyspieszają  też wahania temperatury. W słońcu wnętrze panelu nagrzewa się do temperatury nawet 60-70 C, a nocą spada poniżej temperatury otoczenia. Przejaśnienia w ciągu dnia też powodują wahania temperatury. Przy ogrzaniu najbardziej  chce się wydłużyć metalowy pasek odbierający prąd z warstwy krzemu powodując naprężenia mechaniczne. Test PVEL obejmują 50 cykli przy ekstremalnych różnicach temperatur (od -40°C do +85°C). Dodatkowo przeprowadza się 10 prób przy wysokiej wilgotności, po wystawieniu na wysoką temperaturę i wilgotność panel jest szybko głęboko zamrażany.
Słabym miejscem PV jest tylna plastikowa płyta. Plastik wrażliwy jest na degradujące promieniowanie UV i warunki środowiskowe. Może się nawet zapalić co się zdarza. Przez powstałe szczelinki i szczeliny w plastiku wnika do PV wilgoć a ona szybko prowadzi do korozji, zwarć i uszkodzenia samych ogniw. O wiele lepszym ale droższym rozwiązaniem jest tylna szyba.
Testy wymuszają uszkodzenia jakie powstaną w PV w ciągu 10, 20 i 50 lat eksploatacji .
Większość paneli PV na rynku jest mało trwała !

Jakość wyrobów zawsze była ważna i lepsze wyroby były droższe. Ale dopiero masowa produkcja przemysłowa przyniosła systematyczne podejście do jakości projektu - produkcji i niezawodności. Nowe rozwiązanie ( także materiały ) winno być przetestowane aby uniknąć kosztów dużej ilości napraw gwarancyjnych i utraty marki. 
Rzetelne testowanie programów jest z reguły droższe niż ich stworzenie. Przykładowo Microsoft zbiera dane od użytkowników i dopiero poprawia przeliczne błędy przez nich wykryte. Zbieranie danych z sieci serwisowej i ich analiza celem poprawy błędów jest praktyką stosowaną od wieku i Microsoft niczego nie odkrył.
„Fault Tolerant” w rozdziale „Testy dla oceny niezawodności” podaje przykłady różnych testów. Początkowy fragment:
„Przeprowadzane testy pozwalają ocenić własności urządzeń czyli ich rzeczywistą funkcjonalność i niezawodność,  także w sytuacjach zakłóceniowych i anormalnych. Testuje się urządzenia  użyte do budowy systemów i własności kompletnych systemów.
Oczekiwania od produktów są bardzo różne. Drogi, markowy wyrób powinien być niezawodny. Koszt utrzymania sieci serwisów może być znaczny a kiepski wyrób zepsuje opinie marki i obniży jej wartość. Zatem to czynniki ekonomiczne wyznaczają intensywność i szczelność programu testów. 
Teoretycznym projektowaniem optymalnych testów zajmuje się Inżynieria Niezawodności. Zazwyczaj jednak testy podpowiadają nam realne zdarzenia, intuicja, wiedza i doświadczenie.
Możliwe jest wbudowanie w system własności samotestowania (Built In Self Test, BIST). Już na wczesnym etapie projektu trzeba analizować realizacje zdolności samotestowania tak aby ją sensownie zaimplementować.”

Powtarzalny ( znormalizowany ) proces testu dawno zmechanizowano a potem zautomatyzowano.
Proces testu nowo opracowanego „leku” jest skomplikowany, długotrwały i bardzo kosztowny. Oczywiście trzeba opracować odpowiedni, złożony program komputerowy do dyrygowania badaczami i pacjentami, zbierania i analizy danych z sieci ośrodków badających na pacjentach (!) „lek”. Często odkrywane są dopiero w czasie dłuższych badań na większej populacji ukryte dyskwalifikujące wady i „lek” nie może być wprowadzony na rynek mimo zainwestowania znacznych środków. Słusznie podnoszone są naganne praktyki koncernów farmaceutycznych ale chyba ich agenci rozpowszechniają nonsensowne zarzuty jako choćby że w procesach badań nowych leków zespoły lekarzy badaczy posuwają się on do działań nieetycznych czy wręcz kryminalnych co jest kompletna bzdurą.
Chińskie koncerny stosują superkomputery w poszukiwaniu nowych leków. Podpatrzony na zachodzie proces testowania nowych leków został znacznie ulepszony !

O ile krzywe U(I) pojedynczego ogniwa i panela oświetlonego równomiernie są regularne to przy nierównomiernym oświetleniu jest kilka lokalnych maksimów oddawanej mocy co utrudnia wybranie punktu pracy MPP.
Producenci urządzeń współpracujących z PV wyposażają jest z algorytm mający w punkcie MPP  (maximum power point) uzyskać jak najwięcej mocy z PV.
Producenci podają nieweryfikowalne informacje reklamowe że używają Fuzzy logic, Genetic Algorytm, Artificial Inteligencje  i tym podobne odloty.
 Matlab udostępnił na swojej stronie użytkownikom program do symulacji zachowania PV z regulatorem   i falownikiem.

Stosowanie między panelami PV a siecią energetyczną  izolacji galwanicznej transformatorem przetwornicy jest drogie i pogarsza sprawność toteż popularne są rozwiązania bez izolacji galwanicznej !
W symulowanym rozwiązaniu dla sieci trójfazowej napięcie zasilające mostek trójfazowy wynosi około 600Vdc czyli +300Vdc N -300Vdc. Przy silnym nasłonecznieniu tranzystor – klucz regulatora nie pracuje i zespół szeregowo połączonych paneli daje napięcie circa +300 … -300V. Przy słabszym nasłonecznieniu tranzystor sterowany przebiegiem PWM w układzie podwyższającego regulatora impulsowego stabilizuje napięcie i napięcie z paneli wynosi przykładowo asymetryczne -300 … +250V.
W tym rozwiązaniu na panelach PV nie ma zmiennego napięcia sieciowego i jest znikome napięcie o częstotliwości modulacji PWM i harmonicznych. Filtr LC na wyjściu falownika musi być skuteczny i dodatkowo musi mieć dławik commom aby prąd modulacji PWM nie płynął do linii N sieci co przecież jest zabronione. Używa się najlepszych i niestety drogich materiałów na rdzenie dławików i wybór optymalnej częstotliwości modulacji PWM zależy od rodzaju użytych kluczy. Mostki z tranzystorami IGBT pracują przy mniejszych częstotliwościach a zwiększenie częstotliwości modulacji PWM z szybszymi tranzystorami SiC pozwala zastosować mniejsze i tańsze dławiki oraz zminiaturyzować falownik.
Falowniki takie zawsze mają system bezpieczeństwa detekujący upływ prądu poprzez porażonego człowieka, który dotknął odizolowanych paneli.
Trójfazowy mostek trójpoziomowy invertera zawiera więcej kluczy mocy ale ma lepszą sprawność i  dając mniej harmonicznych PWM pozwala zastosować tańsze dławiki filtrów a jak już powiedziano są one drogie. 
Praktycznie każdy z liczących się światowych koncernów mikroelektronicznych oferuje od ponad dekady układ testowy falownika PV ze swoimi modułami, tranzystorami, procesorami, układami pomiarowymi  i czym się tylko da. Poniżej pokazano rozwiązanie Analog Devices.    

 Zwróćmy uwagę ze zwykle stosuje się 12 kluczowy trójfazowy mostek trójpoziomowy i pokazane rozwiązanie invertera jest nieracjonalne.
Rozwiązania takie nazywa się String (=łańcuch) z racji szeregowego – łańcuchowego połączenia na przykład 18-paneli dający napięcie rzędu 600V czyli -300... +200/300V Moce takich falowników sięgają 200kW a nawet więcej a jednostka mocy jest dość tania. Toteż jednostka mocy wielo - megawatowej elektrowni słonecznej na polu ma rozsądny koszt. Pole z PV jest dobrze ogrodzone aby nikt tam nie wtargnął. Kamera ( także na podczerwień ) z systemem rozpoznawania obrazu może pilnować obiektu i wszcząć Alarm, który po pierwsze spłoszy intruza ryzykującego śmiertelne porażenie. Mechanicznie linie paneli PV tylko pod jednym kątem śledzą ruch Słońca. Jeden napęd do śledzenia jest prosty i tani. Jest to optymalne ekonomicznie rozwiązanie. W trakcie koniecznego okresowego czyszczenia paneli przez przyuczony personel z odpowiednim wyposażeniem i narzędziami cały string jednej linii jest dla bezpieczeństwa zwarty. O wypadek jest raczej trudno.
Gorzej sytuacja wygląda na dużym dachu obiektu komercyjnego lub przemysłowego ale nadal nie jest źle. Dodatkowym niebezpieczeństwem jest ryzyko upadku z wysokości i jednoosobowa praca dla bezpieczeństwa jest zabroniona.
W droższych falownikach jednofazowych panele PV są izolowane transformatorem przetwornicy od sieci. Niestety pod presja wprowadzono barbarzyńską normę pozwalającą budować jednofazowe falowniki bez izolacji od sieci. Oczywiście mają one układ detekujący prąd upływu płynący przez porażoną osobę. Na panelach fotowoltaicznych PV na dachu domu jednorodzinnego jest napięcie stałe i wyprostowane dwupołówkowo fazowe napięcie sieciowe ! Po dachem w pomieszczeniu poziom pola elektrycznego 100 Hz jest taki jaki na poziomie gruntu jest pod linią 115 KV kilkanaście metrów od niej.   

„Tesla” Elona Muska produkująca w małej skali, jak na koncerny globalne, samochody elektryczne od kilku lat oferuje też bardzo drogi Powerwall. W jego obudowie jest akumulator litowo – jonowy oraz falownik sieciowy w konfiguracji bliskiej UPS. Współpraca z PV jest na poziomie instalacji napięcia sieciowego i PV musi już mieć swój inwerter ! Energia z PV ładująca akumulator powerwall przechodzi przez dwa inwertery ( i wejściowy regulator napięcia z PV ) i sprawność siłą rzeczy takiego rozwiązania jest nieciekawa.
Zatem mieszkaniec domku z PV na dachu sam ma połowicznie (!) świadczyć sobie usługi regulacyjne które dotychczas gratis miał dostarczać system energetyczny a tak naprawdę konwencjonalna energetyka.
W Belgii „Powerwall 2” z  akumulatorem o pojemności 13.5 KWh ( akumulator w samochodzie elektrycznym jest wielokrotnie pojemniejszy )  razem z elementami instalacji kosztuje około 11 tysięcy Euro a więc koszmarnie drogo ale w USA około 7 tysięcy dolarów a w Australii 10 tysięcy AUD. 
Jednostka energii w w akumulatorze Powerwall jest około 7 razy droższa niż przemysłowa cena akumulatorów. Wystąpiły już pierwsze pożary Powerwall, które są samozapalne tak samo jak samochody Tesla. Idea Powerwall jest wykluczająca  - kolizyjna z dodatkową funkcjonalnością samochodu elektrycznego z dwukierunkowym przepływem energii między akumulatorem a siecią energetyczną. Konstrukcja Powerwall przypomina stosowany od 50 lat do zasilania komputerów UPS. 
Załóżmy że Powerwall ma trwałość 1000 pełnych cykli ładowania – rozładowania akumulatora czyli totalnie daje usługę regulacyjną do 13.5 KWh x 1000 =13500 KWh energii z PV. W warunkach Belgi usługa regulacyjna do energi 1 KWh kosztuje 11000 / 13 500 =  0.82 Euro / KWh. Obecnie elektrownie dostają około 0.045 Euro / KWh. Czyli usługa regulacyjna do PV jest 18.22 razy droższa niż energia z elektrowni. Istne szaleństwo !

Warto zwrócić uwagę że producenci za łącznością bezprzewodową i ładnymi ekranami ukrywają kompletną pustkę funkcjonalną licząc na to że później opracowany algorytm zostanie odpłatnie dosłany aktualizacją. 

Zwróćmy uwagę że popularyzacja energoelektroniki powoduje hybrydowe scalanie trójfazowych mostków IGBT (Mosfet SiC ) inwertera z driverami i innymi układami a masowe produkowany układ jest bardzo tani. Silniki BLDC  / synchroniczne w nowoczesnych pralkach – suszarkach z pompami ciepła, lodówkach i klimatyzatorach są zasilane z inverterów. 
Gdy za produkcje takiego UPS jak powerwall wezmą się koncerny Wschodniej Azji to cena jego elektroniki gwałtownie spadnie. 

Obecnie stosowane, optymalizowane od lat  akumulatory litowo – jonowe mają płynny elektrolit. Nad bateriami ze stałym elektrolitem pracuje wiele ośrodków naukowych oraz koncernów, głównie motoryzacyjnych. Testowane są już wczesne prototypy. Nowy rodzaj akumulatorów prawdopodobnie zdominuje  rynek w ciągu pięciu lat ale przewidywanie przyszłości jest zajęciem bardzo ryzykownym.  Ich zalety to  krótszy czas ładowania, większą gęstość energii czyli dwukrotnie większe zasięgi samochodów elektrycznych, mniejsze wydzielanie niebezpiecznego ciepła oraz przyszłe obniżenie kosztu produkcji akumulatorów o połowę oraz zmniejszenie ilości substancji toksycznych, łatwość recyklingu.  Nowe akumulatory  liderującej Toyoty rzekomo zapewnią dwa razy większy zasięg samochodu w porównaniu z tradycyjną baterią litowo-jonową tej samej wielkości. Pokaz ma być w 2021 roku a produkcja po 2024 roku.
Wszystkie te optymistyczne  przewidywanie nie muszą się spełnić. Jednak dużo lepsze i tańsze akumulatory niż obecnie spowodują szybki wzrost popularności samochodów elektrycznych
a także systemowych magazynów energii elektrycznej.
Tak czy owak przez energoelektroniką i automatyką są dobre czasy.

Tradycyjnie w energoelektronice największą moc mają tyrystorowe falowniki do linii wysokiego napięcia stałego HVDC, High Voltage DC. Linia przesyłowa prądu stałego ma znacznie mniejsze straty niż linia prądu zmiennego co jest istotne przy bardzo dalekim przesyle. Rekordowe napięcie systemu HVDC wynosi +-800 kV

 Brytyjska firma Xlinks rozważa budowę OZE ( energetyki wiatrowej 3,5 GW  i PV 7 GW oraz potężny magazyn energii  o pojemności 5-20 GWh ) w Maroko o szczytowej mocy 10,5 GW. Energie z nich chce doprowadzić do Wielkiej Brytanii z pomocą kabla HVDC o długości aż 3800 km. Projekt ma dać energię tańszą od pochodzącej z atomu.
Trwają już rozmowy z rządem marokańskim na temat wyboru lokalizacji tych projektów. Firma chce przeprowadzić międzynarodowy przetarg na budowę kabla HVDC. Pierwszy etap mógłby być gotowy w 2027 roku i osiągnąć moc 1,8 GW.
W długim kablu straty energii sięgną 10-12 % a więc niewiele jak na taką odległość. Straty te jednak nie zmniejszą istotnie rentowności projektu. Kabel na prąd zmienny w ogóle nie wchodzi w rachubę. Dotychczas energii elektrycznej  nie przesyłano na tak wielkie odległości.  Pociągnięcia kabla tylko przez obce wody Portugalii, Hiszpanii i Francji ma przyspieszyć pozyskiwanie koniecznych pozwoleń. Koszt projektu jest szacowany na około 18 mld funtów.
Po ukończeniu nowy kabel ma dostarczać 26 TWh energii, czyli 7,5 % zapotrzebowania na nią w Wielkiej Brytanii. Trwają rozmowy z rządem brytyjskim  o wsparciu tego projektu kontraktem różnicowym, ale w grę wchodzą także aukcje.


 Od narodzin komputerów jednym z najczęstszych pod-zadań jest wyszukiwanie informacji. Informacji jest coraz więcej i więcej.  Podczas pisania tekstu program sprawdza ( i podkreśla na czerwono błędne ) czy słowa zakończone w pisaniu są w wybranym Słowniku.
Przykładowo kompilator lub interpreter ( ale też później linker czyli konsolidator ) napotykając w analizowanym tekście nazwę sprawdza czy jest ona już w podręcznym zbiorze nazw i korzysta w działaniu z informacji związanych z tą nazwą - kluczem.
Zbiory z kluczami - nazwami są coraz większe. Aby efektywnie docierać do informacji, dodawać i kasować klucze wraz ze związanymi z nimi informacjami, organizuje się ją w postaci drzew lub tabeli korzystając z funkcji mieszającej czyli Hash w dostępie do tabeli. Funkcja mieszająca (zawężająca  jednokierunkowa funkcja skrótu ) na przetworzyć klucz na liczbę mniejszą od wielkości tablicy gdzie jest indeksem . Oczywiście im bardziej jest zapełniona tablica tym więcej jest kolizji to znaczy pozycja w tabeli wyliczona dla klucza liczba jest już zajęta przez inny klucz.
Funkcja mieszająca jest tym lepsza im dla danego zajęcia tablicy ( tabela rozmiaru p ) daje mniej kolizji które wymagają dalszej  kłopotliwej obsługi systemem łączonych list lub adresowaniem otwartym. Powinna być też szybka jako ze współcześnie zbiory mogą być przepastne ilość kluczy może być liczona w miliardach.

Od lat pięćdziesiątych pojawiło się dużo funkcji mieszających i dość szybko stało się jasne ze ich autorzy nie przetestowali ich starannie a ich użycie jest ryzykowne. Temat jest bardzo szeroki i tutaj nie mamy pretensji do jego wyczerpania.
Peter Kankowski sporządził program ( udostępniając źródła ) do rzetelnej oceny 26 funkcji mieszających  a w tym ( jeśli procesor ją ma a AMD jej nie nie ma w ogóle ) nowej instrukcji procesorów Intela ( od i5 w górę) opisanej w publikacji Intela „ Fast CRC Computation for iSCSI Polynomial Using CRC32 Instruction” 
 Instrukcja ta ma być wydajna i coraz wydajniejsza w nowszych procesorach- „These functions work across an arbitrary range of buffer sizes guaranteeing excellent performance across the range, achieving nearly 3X the performance of a linear implementation of CRC32. For instance, a single core of an Intel® Core™ i5 processor 650 can compute the CRC of a 1024-byte buffer at the rate of 0.145 cycles/byte with a single thread! ”

Do testów szybkości i kolizyjności użyto udostępnionych plików:
-Listę 500 najpopularniejszych angielskich słów z Wiktionary
-Listę 1992 nazw funkcji w systemie Win32
-Listę 500 nazw a000 do a499 ( aluzja do automatycznie generowanych kodów nazw )
-Listę najpopularniejszych słów z długim prefiksem i postfixem ( aluzja do zdobienia nazw przez kompilatory )
-Listę 1842 nazw z WordPress 2.3.2
-Listę wszystkich 3228 słów z Sonetów Szekspira
-Listę słów z "La Peau de chagrin" ( Jaszczur ) Balzaca po francusku w kodowaniu UTF-8.
-Listę adresów IP

Osobno użyto też listy 12.5 miliona kluczy z angielskiej Wikipedii.
Autor dodał listę ponad 300 tysięcy polskich nazwisk oraz z dodatkową liczbą osób je posiadających.
Poniżej przykładowy zrzut ekranu dla procesora Core i5. Tłuste liczby to ilość cykli a blade w nawiasie ilości kolizji.

 Nowsze niż Core i5 procesory są wydajniejsze ale szału niestety nie ma.  
Szybka i mało kolizyjna jest funkcja Larsona ( to pracownik Microsoft ).
Na dużym zbiorze (12.5 mln elementów)  wszystkie niewadliwe funkcje mieszające mają asymptotycznie taką samą kolizyjność a pozostałe są toksycznymi śmieciami.
Według kryterium jakości zaproponowanego przez legendarnych autorów książki o kompilatorach, w żargonie „Red Dragon Book”, większość funkcji mieszających nie jest zła.

Funkcja Larsona ( i kilka innych ) należy do Uniwersalnej Rodziny Funkcji Mieszających zamieniających łańcuch znaków dowolnej długości na liczbę.
uint hash(String x, int a, int p)
        uint h = INITIAL_VALUE
        for (uint i=0 ; i < x.length ; ++i)
                h = ((h*a) + x[i]) mod p
        return h
Wybór wartości INITIAL_VALUE oraz a daje wspomnianą uniwersalność. Rozmiar tablicy p winien być liczbą pierwszą. Dzielenie stałoprzecinkowe ( obliczenie mod p ) jest jednak bardzo powolne i można je zastąpić szybszym kodem.

Funkcja Larsona jest bardzo dobra ale... podle ( niektóre inne też !) zachowuje się dla długich kluczy i gdy takowe są przewidziane nie należy ich stosować. Funkcje Murmur2, Meiyan, Sbox i  z Intelowską instrukcją CRC32 nigdy nie zawodzą ale mogą nie być rewelacyjne w konkretnym zastosowaniu. Czyli w nowych zastosowaniach temat niby rozwiązuje instrukcja CRC32 ale niestety procesory AMD jej nie mają czyli instrukcja ta nie jest rozwiązaniem!

Win32 ma 1992 nazwy funkcji. Systemy takiego stopnia komplikacji nie są często tworzone ale ilość nazw w systemach jednak rośnie. Podobną ilość nazw ma WordPress. IBM w historycznych kompilatorach do swojego super uniwersalnego i super wydajnego języka do wszystkiego PL/1 stosował funkcje mieszającą i tablice pojemności 211 ( warto zauważyć że jest to liczba pierwsza). W PL/1 zaimplementowano Kartoteki rozproszone. 
Czyli programy są coraz bardziej skomplikowane i coraz większa jest ilość zmiennych i funkcji.
Kontener hash_map ( z innych się wycofano ) z STL ( Standard Template Library ) ( unordered associative containers ) implementuje warianty funkcji hash. Działa to tragicznie. 
 

Sprawdzenie:
Fragmenty programu.

UINT HashLarson(const CHAR *key, SIZE_T len) {
    UINT hash = 0;
    for(UINT i = 0; i < len; ++i)
        hash = 101 * hash + key[i];
    return hash ^ (hash >> 16);
}

-Co to jest  SIZE_T ?
-Po co jest  „return hash ^ (hash >> 16)”

UINT Hash_Meiyan(const char *str, SIZE_T wrdlen)
{
    const UINT PRIME = 709607;
    UINT hash32 = 2166136261;
    const char *p = str;

    for(; wrdlen >= 2*sizeof(DWORD); wrdlen -= 2*sizeof(DWORD), p += 2*sizeof(DWORD)) {
        hash32 = (hash32 ^ (_rotl(*(DWORD *)p,5) ^ *(DWORD *)(p+4))) * PRIME;       
    }
    // Cases: 0,1,2,3,4,5,6,7
    if (wrdlen & sizeof(DWORD)) {
        hash32 = (hash32 ^ *(WORD*)p) * PRIME;
        p += sizeof(WORD);
        hash32 = (hash32 ^ *(WORD*)p) * PRIME;
        p += sizeof(WORD);
    }
    if (wrdlen & sizeof(WORD)) {
        hash32 = (hash32 ^ *(WORD*)p) * PRIME;
        p += sizeof(WORD);
    }
    if (wrdlen & 1)
        hash32 = (hash32 ^ *p) * PRIME;
   
    return hash32 ^ (hash32 >> 16);
}

-Dlaczego ta funkcja jest tak szybka mimo długiego tekstu ?
Podpowiedź - Rzuć okiem na wytworzony przez MSVC++ kod

Pytanie ogólne i do wszystkich funkcji.
-Dlaczego wyrównanie adresów tak niewiele ( lub nic ) daje ?
-Jak to jest możliwe że szybszy jest równoważny co do rezultatu kod bez instrukcji dzielenia niż reszta z rozkazu dzielenia ?
-Wymień bardzo bliskie potęgom liczby 2 liczby pierwsze. Jak one się nazywają ?
-Jakie zdumiewająco wolne rozkazy mają procesory rodziny '86.


Ćwiczenie

1.Istnieją ( schematy i dokumentacje ) przynajmniej trzy generacje urządzeń UPS Smart APC.
UPS może być obciążony żarówką 200 W lub komputerem biurkowym a zasilany jest z regulowanego autotransformatora ( napięcie podano też do DVM ) z wyłącznikiem a jego napięcie wyjściowe obserwowane jest oscyloskopem.
-Dlaczego przy obciążeniu komputerem PC napięcie wyjściowe z invertera UPS jest trochę zniekształcone ?
-Przy jakich napięciach wejściowych działają funkcje Trim i Boost ?
-Przy jakich napięciach wejściowych podejmuje prace inwerter UPS ?
-Jaki jest czas reakcji UPS na zniknięcie ( wyłącznik !) napięcia wejściowego i od czego on zależy ? Dlaczego tylko kątem oka widać przy przełączeniu delikatne mrugnięcie zasilanej żarówki ?
-Dlaczego napięcie z invertera UPS jest ( przynajmniej początkowo ) w fazie ze „znikniętym” napięciem sieciowym ?
-Dlaczego napięcie invertera UPS przed przełączeniem na sieć zasilająca zostaje z nią zsynchronizowane jeśli w długim czasie fazy napięć się rozjechały ?
-W jaki sposób ( zapoznać się ze schematami generacji urządzeń ) uzyskano krótki czas wyłączenia przekaźnika odłączającego sieć zasilającą  przy zaniku jej napięcia ?
-Którym przekaźnikom celowo i po co zwiększono czas odpuszczenia ?
-Na schematach  część układów scalonych oprócz cyfrowego kodu producenta ma też komercyjną nazwę producentów. Mimo tego niektóre układy komercyjne na schemacie mają tylko cyfrowy kod producenta ale nie są produkowane wyłącznie dla APC choć system zawiera układy projektu APC produkowane tylko dla niego. Na najstarszym schemacie dopisano komercyjne nazwy układów. Należy odnaleźć na nowszych schematach te układy.
-Co i gdzie detekuje układ „Site Wiring Fault”
-Wskaż elementy LC filtru modulacji PWM.
Jaki rodzaj modulacji PWM do jednofazowego mostka daje najmniej intermodulacji co pozwala oszczędzić na filtrze LC i stratach mocy w nim ? Czy częstotliwość modulacji jest stała ?
-Czy zadanie programowej oceny ilości energii pozostałej w akumulatorach ( oraz czasu działania przy danym obciążeniu ) jest proste do wykonania ? Jak to wygląda dla różnych rodzajów akumulatorów ?
-Pokaż przykłady zastępowania w generacjach układów elektronicznych UPS scalonymi peryferiami mikrokontrolera i programem.
-Różne urządzenia są produkowane w różnych wersjach i na różne rynki świata z różną obsadą elementów. Na skomplikowanym schematach kolejnych generacji UPS pokazano jednak wszystkie elementy wszystkich wersji ( w konkretnym urządzeniu jest tylko część pokazanych na schemacie elementów )  co mocno zmniejsza jego czytelność. Elektroniczne koncerny światowe w takiej sytuacji radzą sobie lepiej stosując różne środki. Jakie to są środki ?

Brak komentarzy:

Prześlij komentarz