بخشی از مقاله
سیستم های گرامر ارتباط موازی
لیلا سانتیان
تلاشهایی برای یافتن یک مدل مناسب برای پردازش موازی انجام شده است. نظریه اتوماسیون سلولی، سیستم های Lindenmayer، اتوماسیون شبکه سیستول، و گرامرهای موازی روسی و موازی هندسی مثالهایی از این مدل ها بر مبنای یک زبان رسمی و تئوری های اتوماسیون هستند. در این دستگاه ها، موازی بودن هدف اصلی است. علائم بصورت مستقل از هم نوشته می شوند. هیچ همکاری اصلی بین فرآیند های موازی رخ نمی دهد، اگرچه برای مثال، در سیستم های L دارای روابط متقابل، نوعی از همکاری دیده می شود.
البته توسعه سیستم های پردازش موازی تا حد زیادی اهمیت ارتباط میان-پردازنده ای را در طرح نسل جدید از کامپیوترها افزایش داده است. ارتباط نقش اصلی را در ساختارهای پردازش موازی ایفا میکند، که توپولوژی روابط داخلی نامناسب می تواند باعث افزایش طول مسیرها شود، قابلیت اطمینان سیستم را کاهش دهد و محدودیت های کارایی پیچیده تری را ایجاد کند.
سیستم های همکاری/سیستم های گرامر توزیع شده تلاشی برای مدلسازی فرآیند ارتباط به شمار می آیند. آنها از یک سیستم از گرامرهایی تشکیل شده اند که با هم کار میکنند تا کلمات یک زبان را تشکیل دهند. هر کدام از گرامرها، صورت های جمله ای را بازنویسی میکند تا شرایط خاص و مورد نظر بدست آید. سپس آنرا به مرحله بعدی از گرامر می فرستد و به همین ترتیب، تا اینکه یک رشته نهایی بدست آید. این مدل دارای ویژگی های اصلی فرآیند ارتباط است، اما گرامرهای فردی بصورت متوالی با هم کار میکنند از این لحاظ که، در هر لحظه فقط یک گرامز اجازه دارد که صورت جمله ای را بازنویسی کند.
هدف سیستم های گرامر ارتباط موازی اینست که ایده های موازی بودن و ارتباط را با هم ترکیب کند و یک مدل مناسب برای بررسی های تئوری خصوصیات سیستم های پردازش موازی ایجاد کند.
سیستم های گرامر ارتباط موازی از موارد زیر تکامل پیدا کرده اند:
- سیستم های پردازش دانش توسط یک همکاری اساسی بین برنامه نویسی منطقی و عمکلردی توصیف می گردند، که نیازمند اصول ارتباط مناسب می باشد.
- شرایط مورد نیاز برای پردازش دانش بر مبنای حل مسئله، دارای ماهیت های مختلفی هستند و سیستم های موازی ناهمگنی را ایجاد میکنند.
- اگرچه ارتباط میان فرآیندی را میتوان در سطح فرآیند بررسی کرد، با اینحال نظارت کلی برای توزیع مؤثر کار، تخصیص منابع و مدیریت لازم است.
سیستم های گرامر ارتباط موازی در منبع شماره 16 معرفی شده است و خصوصیات آنها مانند توان تولیدی، پیچیدگی نحوی، خاتمه با توجه به عملیات مختلف، و مسائل تصمیم گیری در منابع [1], [5], [11]—[17], [20] مورد مطالعه قرار گرفته اند.
یک PCGSاز درجه n از n سیستم بازنویسی مجزا (مانند گرامر چامسکی) تشکیل شده است. یکی از گرامرها شناسایی می گردد: زبانی که توسط همکاری با گرامرهای دیگر ایجاد می گردد، زبان سیستم است. هر گرامر فهرست واژگان، اصول بدیهی و قوانین بازنویسی خاص خود را دارد. چون صورت های جمله ای را میتوان بین گرامرها انتقال داد، هیچ علامت پایانی از یک گرامر برای گرامر دیگر بصورت غیرپایانی نخواهد بود.
گرامر در یک PCGSبصورت موازی عمل میکند و هر کدام از آنها از اصل بدیهی خود، در شرایط تعریف شده و در ارتباط با بقیه آغاز می گردد. لحظه های ارتباط به علائم جستجو بستگی دارد که در صورت های جمله ای ایجاد شده توسط گرامرها ظاهر می گردد. علائم جستجو بصورت غیرپایانی خاص هستند که از 1 تا n وارد می گردند و مربوط به گرامر هستند. چنین علائمی ممکن است به فهرست واژگان غیرپایانی هر گرامری تعلق داشته باشد (بجز گرامری که دارای شاخص ورودی آن است).
ظاهر یک علامت جستجو در هر صورت جمله ای معنای ارتباط را با خود دارد، چون علائم جستجو غیرپایانی هایی هستند که نمی توان آنها را بازنویسی کرد. یک ارتباط از جایگزینی همه علائم جستجو با رشته های جاری گرامرهای ارجاعی تشکیل شده است. البته محدودیتی نیز وجود دارد: هیچ جایگزینی برای صورت های جمله ای حاوی علائم جستجو رخ نمی دهد که مربوط به رشته های حاوی علائم جستجوی بیشتر هستند. ارتابطات دایره ای پذیرفته نی شوند. وضعیت گرامری که رشته جاری را فرستاده است به نوع PCGS بستگی دارد. گرامر ممکن است عملکرد خود را ادامه دهد و یا اینکه رشته خود را حذف کند و کار خود را دوباره از اصل بدیهی از سر بگیرد. زبان ایجاد شده توسط PCGS شامل همه رشته های خروجی ایجاد شده توسط گرامر تشخیصی (صرفنظر از وضعیت بقیه) می باشد.
ما تعریف PCGS را بیان میکنیم که:
- مؤلفه های آن جزو گرامر چامسکی است.
- گرامرهای ارسالی کار خود را ار اصل بدیهی از هر ارتباط دوباره از سر می گیرند.
- گرامر ها بصورت همزمان کار می کنند.
تعریف 1 – یک PCGS با درجه بصورت چندتایی-n است
که هر یک گرامر چامسکی است، ، بطوریکه برای همه ، و یک سری از ، از علائم جستجوی وجود دارد.
تعریف 2 – یک پیکربندی در PCGS با درجه n از چندتایی-n
با توجه به محتوا، ما مؤلفه i را گرامر یا بصورت رشته آن در پیکربندی جاری نامگذاری میکنیم. اگر x یک رشته در الفبای باشد، نشاندهنده تعداد رخدادهای حروف در x خواهد بود.
تعریف 3 –برای پیکربندی ما در یک PCGS ، ، می توانیم بنویسیم
اگر یکی از متن های موردی وجود داشته باشند:
(i) برای همه و برای هر ، ما داریم یا در گرامر ، و یا و ؛
(ii) یک وجود دارد، بطوریکه ؛ پس برای هر i مینویسیم ، با ، ، سپس و ؛ وقتی که برای بعضی از j ها ، پس ؛ برای همه شاخص های باقیمانده r، مینویسیم .
یک مشتق گیری از دو مرحله تشکیل شده است: 1) بازنویسی و 2) ارتباط. اگر هیچ علامت جستجویی در مؤلفه ها ظاهر نشود، ما مرحله بازنویسی را انجام میدهیم که از مرحله بازنویسی در هر یک از گرامرها تشکیل شده است. اگر یکی از مؤلفه ها بصورت یک رشته پایانی باشد، بدون تغییر باقی می ماند، درحالیکه بقیه مرحله بازنویسی را انجام میدهند. اگر در یکی از مؤلفه ها هیچکدام از غیرپایانی ها را نتوانیم دوباره بازنویسی کنیم، مشتق گیری بسته می شود.
اگر در هیچکدام از مؤلفه ها یک علامت جستجو وجود نداشته باشد، مرحله ارتباط اجرا می شود که از جایگزینی همه رخدادهای علائم جستجو با مؤلفه های ارجاعی تشکیل شده است. یک مؤلفه فقط زمانی تغییر داده می شود که همه رخدادهای آن از علائم جستجو مربوط به رشته ها بدون علائم جستجو باشد. در یک عملیات ارتباطی، رشته های ارتباطی با علائم جسجوی مطابق با آن جایگزین می گردند. پس از ارتباط، گرامرهای ارسالی کار خود را از اصل بدیهی دوباره از سر می گیرند. اگر همان علائم جستجو در این مرحله بدست نیایند، ممکن است در یکی از مراحل بعدی بدست آیند. مراحل ارتباط انجام می شوند تا اینکه هیچ علائم جستجوی دیگری موجود نباشد. هیچ بازنویسی مجاز نیست اگر علامت جستجو در یکی از مؤلفه های پیکربندی رخ دهد. بنابراین اگر جستجوهای دایره ای ظاهر شود، مشتق گیری متوقف می شود.
تعریف 4 – زبان ایجاد شده توسط بصورت زیر می باشد:
اگر ما این محدودیت را داشته باشیم که فقط گرامر اول می تواند درخواست ایجاد رشته ها توسط بقیه را داشته باشد، خواهد بود، و ما می گوییم که یک PCGS مرکزی است؛ برعکس، مورد بدون محدودیت غیر مرکزی نامیده می شود.
بعلاوه، تعاریف بالا مربوط به PCGS های بازگشتی هستند. یک PCGS بصورت غیربازگشتی خواهد بود اگر ما در نقطه (ii) از تعریف این عبارت ها را حذف کنیم: . این بدین معناست که پس از ارتباط، گرامر به باز نمی گردد، بلکه پردازش رشته جاری را ادامه می دهد.
یک PCGS بصورت منظم، دارای محتوای آزاد، حساس نسبت به محتوا، آزاد از و غیره است، وقتی که همه مؤلفه های گرامر از این انواع باشند. با توجه به محتوا، REG, LIN,CF,CS,RE بترتیب نشاندهنده طبقات زاویه ای آزاد از ، خطی آزاد از ، محتوای آزاد از ، حساس نسبت به محتوا، گرامرهای بازگشتی، و خانواده زبان های ایجاد شده توسط آنها هستند. اگر زیرنویس λ اضافه گردد، ما به این گرامرها رجوع میکنیم که شامل قوانین λ هستند. فرض کنید که x یکی از طبقات گرامری ذکر شده در بالا باشد. ما بعنوان خانواده زبان های تولید شده توسط PCGS بازگشتی غیر مرکزی از نوع x با درجه در نظر می گیریم؛ وقتی از PCGS مرکزی استفاده شود، خانواده های مطابق با آنها بصورت نشان داده می شوند. وقتی که PCGS غیربازگشتی در نظر گرفته شود، ما خانواده های را نشان میدهیم. و همچنین
و همچنین برای CPC,NPC,NCPC نیر اینطور می باشد (خانواده های زبان های تولید شده توسط PCGS با انواع داده شده با درجه اختیاری).
مثال 1 – فرض کیند که باشد که
یک مشتق مطابق با π دارای شکل زیر خواهد بود:
ما مشاهده میکنیم که اگر در پیکربندی اعمال گردد پس مشتق گیری متوقف می گردد:
و را نمی توان در بازنویسی کرد. همان اتفاق خواهد افتاد اگر ما قانون را در پیکربندی اعمال کنیم. ما نتیجه گیری میکنیم که
که یک PCGS زاویه ای غیرمرکزی از درجه 3 است.
مثال 2 –PCGS زاویه ای غیر بازگشتی مرکزی را در نظر بگیرید که
مشتق ها در دارای یکی از شکل های زیر خواهند بود:
بعبارت دیگر
که یک زبان با محتوای غیر آزاد است.
همانطور که از مثال بالا مشخص است، توان تولیدی PCGS خیلی بیشتر از توان تولیدی مؤلفه های بازنویسی مطابق با آن است: یک PCGS با دو یا سه مؤلفه گرامری منظم می تواند زبان هایی با محتوای غیر آزاد تولید کند. این بدین معناست که افزایش تعداد مؤلفه ها، قدرت تولیدی را بیشتر می کند، یا بعبارت دیگر، موازی بودن و ارتباط دارای کاربرد عملی هستند. در منبع 20 اثبات شده است که مرتبه بندی طبقات زبان های تولید شده توسط PCGS بازگشتی منظم بصورت نامتناهی است، که یک طبقه توسط تعداد مؤلفه ها تعیین می گردد.برای مورد مرکزی، این اثبات از نتیجه کمکی زیر استفاده میکند:
قیاس منطقی 1 – فرض کنید L یک زبان در سات. تعداد طبیعی از N وجود دارد بطوریکه هر کلمه در L را می توان بصورت زیر تجزیه کرد
که
در L قرار دارد برای همه .
البته برای مورد غیرمرکزی مثال مستقیمی را باید بکار برد و قیاس متطقی مشابهی را نمی توان اثبات کرد. برای مورد حساس نسبت به محتوا ما هیچ مرتبه بندی نخواهیم داشت که در منبع 1 اثبات گردد، که
روابط بین طبقات زبان های تولید شده توسط PCGS و خانواده های زبان های دیگر:
- با مطابقت ندارند
- با مطابقت ندارند
- شامل می باشد
- عر زبان در بصورت نیمه خطی است
- خانواده های شامل زبان های غیر نیمه خطی هستند
- شامل زبان هایی است که دارای ماتریس غیر خطی ساده ای نیستند
- شامل زبان هایی نیست که دارای ماتریس ساده نیستند (برای تعاریف به منبع 19 مراجعه کنید).
ما تا کنون فقط در مورد افزایش در قدرت تولیدی بدست آمده توسط موازی کردن (بدون توجه به درجه ارتباط) بحث کرده ایم. پارامتر com معرفی نشده است و در منابع 14 و 17 بعنوان سنجشی از ارتباط مورد مطالعه قرار گرفته است.
تعریف 5 – یک و مشتق در را در نظر بگیرید:
با دلالت بر:
چون تعریف میکند
پس
و برای زبان L و طبقه
پارامتر com تعداد کلی علائم جستجو را ارزیابی میکند که در یک مشتق ظاهر می گردد. ما فقط PCGS بازگشتی مرکزی را در نظر می گیریم، بنابراین ما طبقه x از PCGS را مشخص نمی کنیم و com را برای می نویسیم. قضیه زیر بیان میکند که افزایش ارتباط بر روی قدرت تولیدی تأثیر می گذارد:
قضیه 1 - ، شامل می باشد.
یک نتیجه کلی تر که تأثیر پارامتر com را نشان میدهد قضیه زیر است:
قضیه 2 – اگر یک PCGS بازگشتی زاویه ای باشد، بطوریکه ، پس دارای محتوای آزاد خواهد بود.
همانطور که از مثال 1 مشخص است، PCGS زاویه ای می تواند زبان های دارای محتوای غیر آزاد را نیز تولید کند، بنابراین در این مورد فقط ارتباط سبب افزایش در توان تولیدی شده است.
یک خصوصیت جالب دیگر که (مانند موازی بودن و ارتباط) میتواند قدرت PCGS را تغییر دهید، همزمان سازی است. تا کنون ما فقط مشتق های همزمان را در یک PCGS بررسی کرده ایم، یعنی اینکه هر گرامر دقیقاً فقط از یک قانون در مرحله مشتق گیری استفاده می کند، که تنها مؤلفه ای است که ممکن است منتظر تبدیل شدن به مؤلفه پایانی باشد. در مورد زمانی که گرامر ها ممکن است بدون محدود منتظر بمانند چطور؟ این مسئله توسط جی. هروموکویک بیان شده است که در منبع 11 توضیح داده شده است. اصولاً برای تعریف یک مشتق همزمان سازی شده در یک ، ما شرایط (i) را در تعریف 3 بصورت زیر جایگزین می کنیم:
، و برای هر i، ، ما را در گرامر و یا خواهیم داشت.
نشاندهنده زبان های تولید شده به این شیوه است.
مثال 3 –PCGS غیر همزمان غیر بازگشتی مرکزی با محتوای آزاد را در نظر بگیرید، با
