இரவல் வாங்கிய நிரம்பிய வட்டு கணினிகளை வேகமாக்குகிறது

சில சிக்கல்கள் நேரத்தில் மலிவானவை, ஆனால் நினைவகத்தில் பேராசை கொண்டவை; சில நேர்மாறானவை. சில அடிப்படைப் பணிகளுக்கு, இந்த இடைமாற்றத்தின் மீது கோட்பாட்டாளர்கள் கடுமையான வரம்புகளை நிரூபித்துள்ளனர்: சிறிய வேலை நினைவகத்துடன் நீங்கள் வேகமாக இருக்க முடியாது. ஒரு விசித்திரமான வளம், அதாவது ஏற்கெனவே நிரம்பியுள்ள, சேதமின்றித் திருப்பித் தரப்பட வேண்டிய நினைவகம், அந்த வரம்புகளை உடைக்கிறது என்று ஒரு புதிய ஆய்வுக்கட்டுரை காட்டுகிறது.

இரவல் வன்வட்டு

இந்த மாதிரி வினையூக்கிக் கணிப்பு (catalytic computing) எனப்படுகிறது; 2014-இல் புர்மன், க்ளீவ், கௌட்ஸ்கி, லோஃப், ஸ்பீல்மன் ஆகியோர் இதை அறிமுகப்படுத்தினர். ஒரு நெறிமுறைக்கு, n அளவு உள்ளீட்டுக்கு log n பிட்கள் அளவிலான ஒரு சிறிய சுத்தமான நினைவகமும், அது தேர்ந்தெடுக்காத தன்னிச்சையான தரவால் ஏற்கெனவே நிரம்பிய ஒரு பெரிய அழுக்கு நினைவகமும் கிடைக்கின்றன. இரண்டையும் அது விரும்பியபடி பயன்படுத்தலாம், ஆனால் அது நிற்கும்போது, அழுக்கு நினைவகத்தின் ஒவ்வொரு பிட்டும் முன்பு இருந்தது போலவே சரியாக இருக்க வேண்டும்.

ஆசிரியர்கள் வழக்கமான உருவகத்தைப் பயன்படுத்துகின்றனர்: ஒரு கணக்கீட்டை இயக்க, விலைமதிப்பற்ற டிஜிட்டல் நினைவுகளால் நிரம்பிய ஒரு நண்பரின் மிகப்பெரிய வன்வட்டை இரவல் வாங்குகிறீர்கள். நண்பரை இழக்க நீங்கள் விரும்பவில்லை, எனவே முடித்ததும் ஒவ்வொரு பிட்டையும் மீட்டமைக்கிறீர்கள்.

இந்த மாதிரி முதலில் அத்தகைய நினைவகம் பயனற்றது என்று நிரூபிப்பதற்காகவே உருவாக்கப்பட்டது. உள்ளுணர்வாக, எல்லாவற்றையும் மீட்டமைக்க எல்லாத் தகவலையும் வைத்திருக்க வேண்டும், எனவே எந்த இடத்தையும் ஒருபோதும் விடுவிக்க முடியாது. வியப்பூட்டும் வகையில், நேர்மாறானதே உண்மை எனத் தெரியவந்தது: சுத்தமான நினைவகத்தை மட்டும் கொண்டு எப்படித் தீர்ப்பது என்று யாருக்கும் தெரியாத சிக்கல்களை நிரம்பிய நினைவகம் தீர்க்க உதவுகிறது. ஆனால் அந்த முடிவுகள் இடம் (நினைவகம்) பற்றியவை, நெறிமுறைகளோ மிக மெதுவானவை.

நிரூபிக்கப்பட்ட சாத்தியத்தை விட வேகமாக

அடெல்மோ மோரிசன் ஒரோஸ்கோ, நேதன் ஷெஃபீல்ட், ரயன் வில்லியம்ஸ் (MIT) இப்போது வேகத்தைப் பார்க்கின்றனர். மடக்கை அளவு சுத்தமான நினைவகமும் பல்லுறுப்புக்கோவை அளவு இரவல் நினைவகமும் கொண்டு, அவர்கள் பின்வருவனவற்றைச் செய்யும் நெறிமுறைகளைத் தருகின்றனர்:

• ஒரு பட்டியலை வரிசைப்படுத்துதல், ஒரு தனித்த ஃபூரியே உருமாற்றம் கணக்கிடுதல், n^(1+o(1)) நேரத்தில், அதாவது கிட்டத்தட்ட நேரியல்;
• அணிகளைப் பெருக்குதல், n^(ω+o(1)) நேரத்தில், அதாவது வரம்பற்ற நினைவகத்துடன் அறியப்பட்ட சிறந்த முறையின் வேகத்தில்.

இரவல் வட்டு இல்லாமல், நேரம், நினைவகம் இரண்டின் பெருக்கல் வரிசைப்படுத்தலுக்கும் ஃபூரியே உருமாற்றத்துக்கும் குறைந்தது n² அளவிலும், அணிப் பெருக்கலுக்கு n³ அளவிலும் இருக்க வேண்டும் என்பது நிரூபிக்கப்பட்டுள்ளது. ஆகவே இந்த வினையூக்கி நெறிமுறைகள், எந்தச் சாதாரணச் சிறிய நினைவக நெறிமுறையும் எட்ட முடியாத வேகங்களை எட்டுகின்றன. வினையூக்கி நெறிமுறைகள் வினையூக்கி அல்லாதவற்றை விஞ்சுகின்றன என்பதற்கான முதல் நிபந்தனையற்ற நிரூபணம் இது என்று ஆசிரியர்கள் கூறுகின்றனர்.

மாற்று, படி, செயல்தவிர்

முக்கியக் கூறு ஒரு சிறிய சேர்வியல் உத்தி. ஒரு நெறிமுறை, இரவல் நினைவகத்தின் ஒரு பகுதியை அறியப்படாத மதிப்பு τ-க்கும் τ + x-க்கும் இடையே மாற்ற முடியும் என்று வைத்துக்கொள்வோம்; இங்கு x என்பது அதற்குத் தேவையான முடிவு. இரவல் வாங்கப்பட்ட ஒரு பெரிய “உதவி” அட்டவணையில், கவனமாகத் தேர்ந்தெடுக்கப்பட்ட உள்ளீடுகளின் ஒரு கணத்துக்கு 1 கூட்டுங்கள். τ நிலையில் உள்ள உள்ளீடு, x ஒரு குறிப்பிட்ட கணத்தைச் சேர்ந்தது என்றால், என்றால் மட்டுமே ஒன்று உயர்கிறது. பிறகு ஒவ்வொரு படியையும் பின்னோக்கி இயக்குங்கள்; நீங்கள் விரும்பிய விடையின் அந்த பிட் தவிர, வட்டு முன்பு போலவே இருக்கும்.

இந்த உத்தியை அடுக்கு அடுக்காக அடுக்குவது ஆழமற்ற சுற்றுகளை விரைவாக மதிப்பிடுகிறது. பின்னர் ஆசிரியர்கள் வரிசைப்படுத்தும் வலையமைப்புகள், வேகமான ஃபூரியே உருமாற்றங்கள், வேகமான அணிப் பெருக்கல் ஆகியவற்றை அத்தகைய சுற்றுகளாக மாற்றியமைக்கின்றனர். எண்கணிதத்தில், இரண்டு அறியப்படாதவற்றைப் பெருக்கும் அடுக்குகளுக்கு மட்டுமே கூடுதல் செலவு; முற்றிலும் நேரியலான அடுக்குகள் கிட்டத்தட்ட இலவசம்.

நியாயமான ஒப்பீடு

ஓர் எதிர்ப்பு: பாரம்பரிய வரம்புகள், விடை ஒரு தனி வெளியீட்டு நாடாவில் இடமிருந்து வலமாக ஒரே ஒரு முறை எழுதப்படுவதாகக் கருதுகின்றன; வினையூக்கி நெறிமுறைகளோ தங்கள் விடையை இரவல் வட்டில் எழுதுகின்றன. ஆய்வுக்கட்டுரை இதைக் கையாள்கிறது. தங்கள் நெறிமுறைகள் ஒரு வெளியீட்டு நாடாவின் மீது இரண்டு கடப்புகளில் விடையை எழுத முடியும் என்றும், சாதாரண நெறிமுறைகளுக்கு இரண்டு கடப்புகள் ஒன்றை விட அதிகம் உதவுவதில்லை என்றும் ஆசிரியர்கள் காட்டுகின்றனர். ஆகவே வரம்புகள் இன்னும் பொருந்துகின்றன, பிரிவும் நிலைக்கிறது. இரவல் வட்டு இருந்தாலும் ஒரு கடப்பு போதாது என்றும் அவர்கள் நிரூபிக்கின்றனர்: அப்போது வரிசைப்படுத்தல் அதே n² தடையில் மோதுகிறது.

பயனடைவோரின் நீண்ட பட்டியல்

அதே கருவிகள், பெரிய முழு எண்களையும் பல்லுறுப்புக்கோவைகளையும் பெருக்குதல், வலையமைப்புகளில் முக்கோணங்களை எண்ணுதல், கிளிக்குகளை (clique) கண்டறிதல், பாதைகளையும் சுழற்சிகளையும் கண்டறிதல், வைல்டுகார்டுகள் கொண்ட உரை வடிவங்களைப் பொருத்துதல் ஆகியவற்றுக்கு வேகமான வினையூக்கி நெறிமுறைகளைத் தருகின்றன. அவற்றின் இயக்க நேரங்கள், சிறிய காரணிகள் வரை, தாம் விரும்பும் அளவு நினைவகம் கொண்ட அறியப்பட்ட சிறந்த நெறிமுறைகளுடன் பொருந்துகின்றன. ஒவ்வொரு நிலையிலும், இரவல் நினைவகம் இரவல் கொடுக்கப்பட்டபடியே சரியாகத் திரும்பி வர வேண்டும்.