Қатарлы есептеулердегі белгісіздік және логикалық шешімдердің ролі
Indeterminacy in concurrent computation
Қатар есептеудегі белгісіздік, желілік жүйелерде және көп ядролы процессорларда маңызды. Есептеу мен логикалық қорытынды арасындағы байланыс зерттеледі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бір мезгілде есептеудегі белгісіздік – бір мезгілде есептеудегі белгісіздіктің салдарымен айналысады. Есептеу – желілік байланыстар мен көп ядролы компьютерлік архитектуралардың дамуына байланысты бір мезгілдестік артуының нәтижесінде белгісіздіктің маңызды бола бастаған саласы. Мұндай компьютерлік жүйелер арбитрлерді қолданады, бұл белгісіздік тудырады.
Indeterminacy in concurrent computation is concerned with the effects of indeterminacy in concurrent computation. Computation is an area in which indeterminacy is becoming increasingly important because of the massive increase in concurrency due to networking and the advent of many core computer architectures. These computer systems make use of arbiters which gives rise to indeterminacy.
Логикалық бағдарламалаудың шектелуі
Патрик Хейз [1973] «есептеу және дедукция процестері арасындағы қалыптанған айқын шекара шатастырады» деген пікірді келтірді. Роберт Ковальски есептеуді дедукцияға бағынуға болатыны туралы тезисті дамытты және «Есептеу – бақыланатын дедукция» деген тұжырымын мақұлдады, оны 1988 жылғы Прологтың бастапқы тарихына арналған мақаласында Хейзге жатқызды. Ковальски мен Хейзге қарсы, Карл Хьюитт логикалық дедукцияның ашық жүйелерде бір уақытта есептеуді жүзеге асыра алмайтынын мәлімдеді. Хьюит [1985] және Ага [1991] және басқа да жарияланған еңбектерде бір уақытта жүзеге асырудың математикалық модельдері нақты бір уақыттағы есептеулерді анықтамайтыны көрсетілді: Актер моделі бірнеше хабарлама бір уақытта жіберілген Актерге келіп түскен хабарламалардың ретін анықтау үшін төрешілік (көбінесе шартты төрешілер түрінде) қолданады. Бұл келу ретіне белгісіздік енгізеді. Келу реті белгісіз болғандықтан, оны тек математикалық логика арқылы алдын ала алынған ақпараттан шығару мүмкін емес. Сондықтан математикалық логика ашық жүйелерде бір уақытта есептеуді жүзеге асыра алмайды. Авторлар математикалық логика, олардың пікірінше, жалпы бір уақыттағы жүзеге асыруды іске асыра алмайды, бірақ бір уақыттағы есептеудің кейбір ерекше жағдайларын іске асыра алады, мысалы, тізбекті есептеу және параллель есептеудің кейбір түрлері, соның ішінде лямбда-есептеу.
Patrick Hayes [1973] argued that the "usual sharp distinction that is made between the processes of computation and deduction, is misleading". Robert Kowalski developed the thesis that computation could be subsumed by deduction and quoted with approval "Computation is controlled deduction." which he attributed to Hayes in his 1988 paper on the early history of Prolog. Contrary to Kowalski and Hayes, Carl Hewitt claimed that logical deduction was incapable of carrying out concurrent computation in open systems. Hewitt [1985] and Agha [1991], and other published work argued that mathematical models of concurrency did not determine particular concurrent computations as follows: The Actor model makes use of arbitration (often in the form of notional arbiters) for determining which message is next in the arrival ordering of an Actor who is sent multiple messages concurrently. This introduces indeterminacy in the arrival order. Since the arrival orderings are indeterminate, they cannot be deduced from prior information by mathematical logic alone. Therefore, mathematical logic cannot implement concurrent computation in open systems. The authors claim that although mathematical logic cannot, in their view, implement general concurrency it can implement some special cases of concurrent computation, e. g., sequential computation and some kinds of parallel computing including the lambda calculus.
Ақпараттың жетіспеушілігіне байланысты логиканың шектеулілігі
Ашық Актер жүйесі – бұл есептеулер ортасында сыртқы Актерлердің мекенжайларын беруге мүмкіндік беретін жүйе, осылайша олар осы сыртқы Актерлермен байланыса алады. Бұл сыртқы Актерлер өз кезегінде, оларға берілген мекенжайларды пайдаланып, жүйенің ішкі Актерлерімен байланыса алады. Келу ретін анықтау мүмкіндігінің шектеулі болуына байланысты, сырттан қандай хабарламалар жіберілгенін білу жүйенің жауабын болжауға мүмкіндік бермейді. Басқа бірнеше жүйелердің модельдері (мысалы, процестік есептеулер) ашық жүйелерді іске асыру үшін қолданылғанда, олардың мінез-құлқы да хабарламалардың келу уақытына байланысты болуы мүмкін, сондықтан оларды логикалық дедукция арқылы іске асыруға болмайды.
An open Actor system is one in which the addresses of outside Actors can be passed into in the middle of computations so that can communicate with these outside Actors. These outside Actors can then in turn communicate with Actors internal to using addresses supplied to them by Due to the limitation of the inability to deduce arrival orderings, knowledge of what messages are sent from outside would not enable the response of to be deduced. When other models of concurrent systems (e. g., process calculi) are used to implement open systems, these systems also can have behavior that depends on arrival time orderings and so cannot be implemented by logical deduction.
Prolog-қа ұқсас бір мезгілдегі жүйелер математикалық логикаға негізделген деп мәлімделген
Кит Кларк, Герве Галлер, Стив Грегори, Виджай Сарасват, Уди Шапиро, Казунори Уэда және т.б. ортақ айнымалыларды біріктіру және хабарламалар үшін дерек құрылымдары ағынын пайдалана отырып, Prolog сияқты бір уақытта жұмыс істейтін хабар алмасу жүйелерінің бірнеше түрін жасады. Бұл жүйелер математикалық логикаға негізделген деген талаптар айтылды. Осындай жүйе Жапонияның Бесінші Буын Жобасының (ICOT) негізі ретінде қолданылды. Карл Хьюит және Гүл Ага [1991] бұл Prolog сияқты бір уақытта жұмыс істейтін жүйелер дедуктивті де, логикалық та емес екенін дәлелдеді: Актер моделі сияқты, Prolog сияқты бір уақытта жұмыс істейтін жүйелер хабар алмасуға негізделгендіктен, сол себепті бірдей анықсыздыққа бейім.
Keith Clark, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog like concurrent message passing systems using unification of shared variables and data structure streams for messages. Claims were made that these systems were based on mathematical logic. This kind of system was used as the basis of the Japanese Fifth Generation Project (ICOT). Carl Hewitt and Gul Agha [1991] argued that these Prolog like concurrent systems were neither deductive nor logical: like the Actor model, the Prolog like concurrent systems were based on message passing and consequently were subject to the same indeterminacy.
Логикалық операциялар және жүйенің тиімділігі
Хьюиттің пікірінше, Prolog және Prolog сияқты бір мезгілде жұмыс істейтін жүйелерден маңызды сабақ алуға болады: бір мезгілдегі есептеудің әмбебап моделі негізгі байланыс механизмдерінде міндетті түрде қосымша жүктеме болса, шектеледі. Бұл – біріктіруді пайдалана отырып, үлгіге бағытталған шақыруды және деректер құрылымы ағынынан хабарламаларды бөліп алуды негізгі амалдар ретінде енгізуге қарсы дәлел. Алайда, Шапироның Prolog сияқты бір мезгілде бағдарламалау тілдері туралы шолуын қарастырыңыз, ол оларды қосудың пайдалылығын көрсетеді.
Hewitt maintained that a basic lesson can be learned from Prolog and the Prolog like concurrent systems: a universal model of concurrent computation is limited by having any mandatory overhead in the basic communication mechanisms. This is an argument against including pattern directed invocation using unification and extraction of messages from data structure streams as fundamental primitives. But compare Shapiro's survey of Prolog like concurrent programming languages for arguments for inclusion.
Басқа есептеу модельдеріндегі белгісіздік
Арбитраж – бір мезгілде есептеудің Актерлік моделіндегі белгісіздіктің негізі (Актерлік модельдің тарихы мен Актерлік модель теориясын қараңыз). Ол процестік есептеулер сияқты бір мезгілде жұмыс істейтін жүйелердің басқа модельдерінде де маңызды рөл атқара алады.
Arbitration is the basis of the indeterminacy in the Actor model of concurrent computation (see History of the Actor model and Actor model theory). It may also play a role in other models of concurrent systems, such as process calculi.