అరువు తెచ్చిన నిండు డిస్క్ కంప్యూటర్లను వేగవంతం చేస్తుంది
కొన్ని సమస్యలకు సమయం తక్కువ పడుతుంది కానీ మెమరీ ఎక్కువ కావాలి, మరికొన్నింటికి దీనికి విరుద్ధం. కొన్ని ప్రాథమిక పనుల విషయంలో, ఈ బేరసారంపై కఠినమైన పరిమితులను సిద్ధాంతకర్తలు నిరూపించారు: పని మెమరీ చిన్నదైతే, మీరు వేగంగా ఉండలేరు. ఒక కొత్త పత్రం ఒక విచిత్రమైన వనరు — అప్పటికే నిండి ఉండి, చెక్కుచెదరకుండా తిరిగి ఇవ్వాల్సిన మెమరీ — ఆ పరిమితులను బద్దలు కొడుతుందని చూపిస్తుంది.
అరువు తెచ్చిన హార్డ్ డ్రైవ్
ఈ నమూనాను ఉత్ప్రేరక గణన (catalytic computing) అంటారు. దీన్ని 2014లో Buhrman, Cleve, Koucký, Loff, Speelman ప్రవేశపెట్టారు. ఒక అల్గారిథంకు చాలా చిన్న శుభ్రమైన మెమరీ లభిస్తుంది, n పరిమాణంలోని ఇన్‌పుట్‌కు సుమారు log n బిట్ల స్థాయిలో; దానితో పాటు, తాను ఎంచుకోని ఏదో ఒక డేటాతో అప్పటికే నిండిన భారీ మురికి మెమరీ కూడా లభిస్తుంది. రెండింటినీ ఇష్టం వచ్చినట్లు వాడుకోవచ్చు, కానీ ఆగిపోయేటప్పుడు, మురికి మెమరీలోని ప్రతి బిట్ ముందు ఉన్నట్లే సరిగ్గా ఉండాలి.
రచయితలు ప్రామాణిక ఉపమానాన్ని వాడతారు: ఒక గణన చేయడానికి, విలువైన డిజిటల్ జ్ఞాపకాలతో నిండిన స్నేహితుడి భారీ హార్డ్ డ్రైవ్‌ను అరువు తీసుకుంటారు. స్నేహితుణ్ని పోగొట్టుకోవాలని మీకు ఉండదు, అందుకే పని పూర్తయ్యాక ప్రతి బిట్‌ను పునరుద్ధరిస్తారు.
మొదట్లో ఈ నమూనా అలాంటి మెమరీ నిరుపయోగమని నిరూపించడానికి ఉద్దేశించింది. సహజంగా ఆలోచిస్తే, అన్నింటినీ పునరుద్ధరించాలంటే మొత్తం సమాచారాన్ని ఉంచుకోవాలి, కాబట్టి ఎప్పటికీ ఖాళీ స్థలం దొరకదు. ఆశ్చర్యకరంగా, దీనికి విరుద్ధమే నిజమని తేలింది: కేవలం శుభ్రమైన మెమరీతో ఎలా పరిష్కరించాలో ఎవరికీ తెలియని సమస్యలను నిండు మెమరీ పరిష్కరించనిస్తుంది. కానీ ఆ ఫలితాలు స్థలం గురించినవి, ఆ అల్గారిథంలు అత్యంత నెమ్మదిగా ఉండేవి.
నిరూపితంగా సాధ్యమైనదానికంటే వేగంగా
MIT కి చెందిన Adelmo Morrison Orozco, Nathan Sheffield, Ryan Williams ఇప్పుడు వేగం వైపు దృష్టి పెట్టారు. సంవర్గమాన (logarithmic) పరిమాణంలోని శుభ్రమైన మెమరీ, బహుపది (polynomial) పరిమాణంలోని అరువు మెమరీతో, వారు ఈ పనులు చేసే అల్గారిథంలను ఇస్తున్నారు:
- ఒక జాబితాను క్రమీకరించడం, విచ్ఛిన్న ఫోరియర్ పరివర్తనను (discrete Fourier transform) n^(1+o(1)) సమయంలో, అంటే దాదాపు రేఖీయ సమయంలో, లెక్కించడం;
- మాత్రికలను గుణించడం n^(ω+o(1)) సమయంలో, అంటే అపరిమిత మెమరీతో తెలిసిన అత్యుత్తమ పద్ధతి అంత వేగంగా.
అరువు డిస్క్ లేకుండా, సమయం, మెమరీల లబ్ధం క్రమీకరణకు, ఫోరియర్ పరివర్తనకు కనీసం n² స్థాయిలో, మాత్రికల గుణకారానికి n³ స్థాయిలో ఉండాల్సిందేనని నిరూపితమైంది. కాబట్టి ఈ ఉత్ప్రేరక అల్గారిథంలు ఏ సాధారణ చిన్న-మెమరీ అల్గారిథం చేరుకోలేని వేగాన్ని చేరుకుంటాయి. ఉత్ప్రేరక అల్గారిథంలు ఉత్ప్రేరకేతర అల్గారిథంలను అధిగమిస్తాయని చూపే మొదటి బేషరతు నిదర్శనం ఇదేనని రచయితలు అంటున్నారు.
మార్చు, చదువు, రద్దు చెయ్యి
కీలకమైన అంశం ఒక చిన్న సంయోజక (combinatorial) చిట్కా. ఒక అల్గారిథం అరువు మెమరీలోని ఒక భాగాన్ని తెలియని విలువ τ, τ + x ల మధ్య మార్చగలదని అనుకుందాం, ఇక్కడ x అనేది దానికి కావలసిన ఫలితం. అలాగే అరువు తెచ్చిన ఒక పెద్ద “సహాయక” పట్టికలో, జాగ్రత్తగా ఎంచుకున్న నమోదుల సమితికి 1 కలపండి. τ స్థానంలోని నమోదు ఒకటి పెరుగుతుంది ఒకవేళ, కేవలం ఒకవేళ మాత్రమే x ఒక ఇచ్చిన సమితికి చెందితే. ఆపై ప్రతి అడుగును వెనక్కి నడపండి; మీకు కావలసిన జవాబులోని ఆ బిట్ తప్ప, డిస్క్ మునుపటిలాగే ఉంటుంది.
ఈ చిట్కాను పొరపై పొరగా పేర్చడం ద్వారా లోతులేని సర్క్యూట్లను వేగంగా మూల్యాంకనం చేయవచ్చు. తర్వాత రచయితలు క్రమీకరణ నెట్‌వర్క్‌లను, వేగవంతమైన ఫోరియర్ పరివర్తనలను, వేగవంతమైన మాత్రికల గుణకారాన్ని అలాంటి సర్క్యూట్లుగా తిరిగి రూపొందిస్తారు. అంకగణితంలో, రెండు తెలియని విలువలను గుణించే పొరలకు మాత్రమే అదనపు ఖర్చు అవుతుంది; పూర్తిగా రేఖీయమైన పొరలు దాదాపు ఉచితంగా వస్తాయి.
న్యాయమైన పోలిక
ఒక అభ్యంతరం: సంప్రదాయ పరిమితులు జవాబును ఒక ప్రత్యేక అవుట్‌పుట్ టేప్‌పై ఎడమ నుంచి కుడికి ఒక్కసారే రాస్తారని ఊహిస్తాయి, కానీ ఉత్ప్రేరక అల్గారిథంలు తమ జవాబును అరువు డిస్క్‌లో రాస్తాయి. పత్రం దీనికి సమాధానం ఇస్తుంది. తమ అల్గారిథంలు అవుట్‌పుట్ టేప్‌పై రెండు దఫాల్లో జవాబు రాయగలవని, సాధారణ అల్గారిథంలకు రెండు దఫాలు ఒక దఫా కంటే ఎక్కువ ఉపయోగపడవని రచయితలు చూపిస్తారు. కాబట్టి పరిమితులు ఇంకా వర్తిస్తాయి, వేర్పాటు నిలిచే ఉంటుంది. అరువు డిస్క్ ఉన్నా ఒక్క దఫా సరిపోదని కూడా వారు నిరూపిస్తారు: అప్పుడు క్రమీకరణ అదే n² అడ్డంకిని ఢీకొంటుంది.
లబ్ధిదారుల పెద్ద జాబితా
ఇవే సాధనాలు పెద్ద పూర్ణాంకాలను, బహుపదులను గుణించడం, నెట్‌వర్క్‌లలో త్రిభుజాలను లెక్కించడం, క్లిక్‌లను (cliques) కనుగొనడం, మార్గాలను, చక్రాలను గుర్తించడం, వైల్డ్‌కార్డ్‌లతో పాఠ్య నమూనాలను సరిపోల్చడం వంటి వాటికీ వేగవంతమైన ఉత్ప్రేరక అల్గారిథంలను ఇస్తాయి. వాటి నడుస్తున్న సమయాలు, చిన్న కారకాల తేడా మినహా, కావలసినంత మెమరీ ఉన్న అత్యుత్తమ తెలిసిన అల్గారిథంలతో సరిపోలుతాయి. ప్రతి సందర్భంలోనూ, అరువు మెమరీ ఇచ్చినప్పుడు ఉన్నట్లే సరిగ్గా తిరిగి రావాలి.