فهرست مطالب

نشریه محاسبات نرم
سال هشتم شماره 2 (پیاپی 16، پاییز و زمستان 1398)

  • تاریخ انتشار: 1399/11/04
  • تعداد عناوین: 6
|
  • محمدپویا اکبرپور*، کیهان خام فروش، وفا میهمی صفحات 2-21

    همواره زمان صرف شده برای حل مسایل سنگین محاسباتی، یکی از دغدغه های برنامه نویسان کامپیوتر بوده است. الگوریتم PSO، الگوریتمی فرا ابتکاری است که به دلیل ساد گی پیاده سازی، برای حل مسایل سنگین محاسباتی استفاده می شود ولی با وجود ساد گی، این الگوریتم برای حل مسایل سنگین واقعی ناکارآمد است. از طرفی، وجود ویژگی تعاملات محلی ذرات در الگوریتم PSO، این الگوریتم را برای موازی سازی مناسب کرده است؛ از طرف دیگر، NVIDIA با اختراع پردازنده گرافیکی و معرفی معماری CUDA، تحولات بنیادی را در حل این نوع مسایل، از طریق پیاده سازی آن بر روی پردازنده گرافیکی ایجاد کرده است. با وجود تمام تحقیقات انجام گرفته در زمینه پیاده سازی، برخی از جنبه های تکنیکی موازی سازی به منظور پیاده سازی الگوریتم به صورتی که تسریع و بازدهی مناسب بر روی تمام پردازنده های گرافیکی NVIDIA را داشته باشد، رعایت نشده است. در این مقاله سعی شده با انتخاب Geforce GT 525M که پردازنده گرافیکی نسبتا ضعیفی است، جنبه مقیاس پذیری روش پیشنهادی رعایت شود؛ به طوری که با رسیدن به بیشینه تسریع الگوریتم پیاده سازی شده بر روی این پردازنده، به بازدهی قابل قبول برای اجرا بر روی سایر پردازنده های گرافیکی رسید. برای نیل به این هدف، از مدل چند کرنلی ارایه شده استفاده شده است. نتایج حاصل از انجام آزمایش ها رسیدن به بیشینه تسریع 15/98 برای حل تابع Rastrigin را نشان می دهد.

    کلیدواژگان: موازی سازی الگوریتم، بهینه سازی اجتماع ذرات، Fermi، GPU Computing، HPC، CUDA
  • سید مجید شفائی*، بابک وزیری، سید مصطفی شفائی صفحات 22-37

    یک انباره داده ای برخط مجموعه ای از داده های اخیر و داده های سلسله مراتبی است که برای اخذ تصمیمات، توسط مدیران از طریق ایجاد پرس و جوهای تحلیلی برخط مورد استفاده قرار می گیرد. داده هایی که از منابع داده ای واکشی می شوند و به انباره داده ای برخط وارد می شوند، روزبه روز در حال افزایش است و همچنین با افزایش حجم داده های ورودی به انباره داده ای برخط تداخل بین عملیات بارگیری و پردازش تحلیلی برخط بیش از پیش افزایش پیدا می کند. این دو چالش به مهم ترین مسایل در زمینه انبار داده ای برخط تبدیل شده اند. در این مقاله، روشی برای بهبود زمان پاسخ دهی پرس و جوهای تحلیلی در معماری انباره داده ای برخط با استفاده از الحاق دیدهای ذخیره شده ارایه شده است. فرایند کار بدین صورت است که نتایج پرس وجوهای اجراشده در هر بخش برخط ذخیره می گردند و در هنگام انتقال داده به بخش بعدی، این نتایج از قبل محاسبه شده نیز منتقل می شوند.  در هنگام انتقال داده، هر بخش برخط حاوی مجموع داده بخش قبلی خود در چندین مرحله از انتقال است. در نتیجه با انتقال داده، نتایج محاسبه شده پرس و جوها نیز منتقل میشوند و می توان بدون نیاز به اجرای دوباره پرس و جوها، نتایج محاسبه شده قبلی را با هم الحاق کرد و به نتیجه دلخواه رسید. روش پیشنهادی منجر به کاهش زمان پاسخ دهی به پرس و جوهای تحلیلی و کاهش تداخل ورود داده با اجرای هم زمان و طولانی مدت پرس و جوها شده است. چالشی که این پژوهش با آن مواجه است، این است که روش پشنهادی بر روی حجم کمی از داده در بخش برخط، مورد استفاده قرار گیرد و همچنین چالش بعدی، شامل تغییرات مورد نیاز برای استفاده در داده بزرگ است.

    کلیدواژگان: انباره داده ای برخط، پردازش تحلیلی برخط، بخش بندی، دید ذخیره شده، مخزن داده
  • مجید محمدپور، بهروز مینایی بیدگلی، حمید پروین* صفحات 38-65

    الگوریتم SSPCO گونه ای از الگوریتم های هوش جمعی و برگرفته شده از رفتار پرنده تیهو است. کارآیی این الگوریتم برای حل مسایل بهینه سازی ایستا به اثبات رسیده است؛ اما این کارآیی این الگوریتم تا به حال برای حل مسایل بهینه سازی پویا مورد آزمایش قرار نگرفته است. به دلیل ماهیت NP-Hard بودن مسایل پویا، این الگوریتم به تنهایی قادر به حل این گونه از مسایل بهینه سازی نمی باشد. بنابراین برای این که الگوریتم قادر به ردیابی بهینه متغیر در این مسایل باشد، باید راهکارهایی به همراه این الگوریتم ارایه داد که بتوانند عملکرد این الگوریتم را درمواجهه با محیط های پویا افزایش دهد. در این مقاله دو راه حل برای ترکیب با الگوریتم SSPCO ارایه شده است که عبارتند از، روش چندجمعیتی و حافظه با تخمین تراکم گوسی. مشکلی که در اکثر روش های چندجمعیتی وجود دارد این است که با افزایش کنترل نشده جمعیت، سرعت و راندمان الگوریتم به تدریج کاهش می یابد. روش چندجمعیتی ارایه شده در این مقاله به صورت تطبیقی با فضای مسئله می باشد، و هر زمان که نیاز به افزایش جمعیت باشد یک جمعیت به صورت تطبیقی ایجاد می شود و این موضوع باعث می شود که مشکل روش های قبلی کاهش یابد. یکی از مواردی که در حل مسایل غیرقطعی باید مشخص شود، استفاده از داده های گذشته نزدیک برای پیش بینی آینده نزدیک است. در این مقاله با توجه به این موضوع برای حفظ اطلاعات گذشته از یک نوع خاصی از حافظه استفاده شده است. در این روش از حافظه جدیدی به نام حافظه تخمین تراکم گوسی استفاده شده است. این حافظه عیوب حافظه استاندارد را برطرف نموده و باعث بهبود کارآیی الگوریتم پیشنهادی می شود. برای آزمایش کارآیی روش پیشنهادی از تابع معروف محک قله های متحرک که رفتاری شبیه به مسایل پویا را شبیه سازی می کند، استفاده شده است. الگوریتم پیشنهادی با 10 تا از مشهورترین الگوریتم های بهینه سازی پویا مقایسه گردیده است. همان گونه که از نتایج تجربی و آزمایش ها مشخص می باشد روش پیشنهادی توانسته خطای برون خطی را تا حدود بسیار زیادی نسبت به سایر روش کاهش دهد و خطای تولید شده برای روش پیشنهادی بسیار ناچیز است.

    کلیدواژگان: الگوریتم SSPCO، محک قله های متحرک، بهینه سازی پویا، خطای برون خطی، حافظه، خوشه بندی، MMSSPCO
  • سجاد اسفندیاری*، وحید رافع صفحات 66-79

    تاکنون، تعداد زیادی الگوریتم مفید برای تولید آرایه پوشش که یکی از شاخه های آزمون ترکیبی ست، ارایه شده است. اصلی ترین چالشدر تولید چنین آرایه هایی، تولید آرایه با تعداد نمونه آزمون کمینه (بهره وری) در زمان مناسب (کارایی)، برای سیستم های بزرگ است. استراتژی های تولید آرایه پوشش قالبا به دو دسته کلی محاسباتی و فرامکاشفه ای تقسیم می شوند. استراتژی های محاسباتی معمولا کارایی بالایی دارند اما از نظر بهره وری نتایج ضعیفی را تولید می کند و استراتژی های فرامکاشفه ای از بهره وری مناسب و کارایی ضعیفی برخوردار هستند. در بین استراتژی های در دسترس استراتژی DPSO از نظر بهره وری بهترین نتایج را دارد، اما کارایی مناسبی ندارد و استراتژی GS کارایی مناسبی را دارد اما بهره وری مناسبی ندارد. در حالت کلی استراتژی که کارایی و بهره وری را توامان داشته باشد، به چشم نمی خورد. در این مقاله ما سعی کردیم با استفاده از توده ذرات دنباله آزمون مناسب را از نظر بهره وری و کارایی، تولید کنیم. همچنین برای افزایش بهره وری از یک تابع کمینه ساز ساده و تاثیرگذار استفاده شده است. نتایج ارزیابی نشان می دهد که راهکار پیشنهادی از نظر کارایی و بهره وری نتایج مطلوب دارد.

    کلیدواژگان: آزمون ترکیبی، تولید داده آزمون، آرایه پوششی، الگوریتم توده ذرات بهینه
  • مصطفی قبائی ارانی*، فاطمه مهدی بابایی صفحات 80-101

    امروزه، پردازش داده های مراقبت های بهداشتی رسانه های بزرگ در ابر به راه حلی موثر برای برآورده کردن تقاضاهای کیفیت سرویس کاربران پزشکی تبدیل شده است. اما فراهم ساختن مراقبت های بهداشتی برای جامعه فعالیتی پیچیده است که شدیدا متکی بر پردازش اطلاعات است و پردازش داده های حوزه سلامت می تواند برای سازمان ها بسیار هزینه بر باشد. بر همین اساس امروزه، پردازش داده های حوزه سلامت رسانه های بزرگ در ابر به راه حلی موثر جهت مرتفع سازی تقاضاهای کیفیت سرویس کاربران حوزه بهداشت و سلامت تبدیل شده است. بر همین اساس در این مقاله، یک راهکار فازی برای تعیین ابر بهینه با استفاده از تکنیک پیش بینی منابع ارایه می شود. همچنین به منظور ایجاد توازن در حین پردازش وظایف از تکنیک مهاجرت ماشین مجازی مبتنی بر انتخابگر فازی جهت انتقال ماشین مجازی از یک سرور با بار زیاد به یک سرور کم بار استفاده می شود. ساختار معماری پیشنهادی شامل دو بخش محلی و سراسری است که برای تحویل درخواست به قسمت سراسری باید ابتدا قسمت محلی بررسی گردد، در صورت نداشتن شرایط، درخواست به قسمت سراسری تحویل داده می شود. در واقع معماری پیشنهادی به صورت سلسه مراتبی عمل می کند و در ابتدا لیست درخواست های رسیده ایجاد می گردد سپس با استفاده از راهکار پیشنهادی، میزان منابع موجود تخمین زده می شود و بر اساس آن، تخصیص منبع جهت پردازش انجام می گیرد. جهت ارزیابی از شبیه ساز Cloudsim استفاده شده است و با توجه به پارامترهای مختلف، راهکار پیشنهادی با الگوریتم های FAHP و ICA-K-Means مورد مقایسه قرار گرفته است. نتایج حاصل از شبیه سازی نشان می دهد که راهکار پیشنهادی در مقایسه با الگوریتم FAHP به میزان 10درصد و نسبت به ICA-K-Means به میزان 12درصد کاهش هزینه بوجود آمده است. همچنین تعداد درخواست های رد شده نیز به همین صورت و به نسبت الگوریتم FAHP به میزان 8 درصد و نهایتا در مقایسه با ICA-K-Means به میزان 7درصد افزایش بهره وری منابع بوجود آمده است.

    کلیدواژگان: تخصیص منابع، رایانش ابری، کنفدراسیون ابر، کیفیت خدمات، انتخابگر فازی، داده های حوزه سلامت
  • شایسته طباطبائی* صفحات 102-115

    شبکه های حسگر بی سیم (WSN) از گره های حسگر با انرژی محدود تشکیل شده است. مصرف بهینه انرژی یک مسئله مهم برای این نوع از شبکه ها است، زیرا گره های حسگر در مناطق ناهموار و بی مراقبت مستقر می شوند و برای ارسال داده ها با ارتباط مستقیم به چاهک انرژی زیادی را صرف خواهند نمود. اخیرا پروتکل IEEE 802.15.4، به عنوان یک استاندارد ارتباطی برای شبکه های حسگر کم مصرف، با نرخ پایین و کم هزینه مورد استفاده قرار گرفته است که ازطریق روش برش زمانی تضمینی (Guaranteed Time Slot)، کاربردهای بلادرنگ را تضمین می کند بر این اساس در این مقاله، یک پروتکل جدید آگاه از انرژی با الگوریتم خفاش (Bat Algorithm) و چاهک متحرک ارایه شده است که قادر به انتخاب مسیر بهینه بر اساس معیار فاصله تا چاهک، شدت صوت و انرژی سطح باتری می باشد. روش پیشنهادی با پروتکل BAT، پروتکل NODIC و استاندارد IEEE802.15.4 در شبیه ساز OPNET ورژن 11.5 شبیه سازی شد و نتایج از نظر انرژی مصرفی، تاخیر انتها به انتها، نسبت سیگنال به نویز، احتمال موفقیت ارسال داده به چاهک و نرخ گذردهی باهم مقایسه شدند. نتایج حاصل از شبیه سازی نشان داد که استفاده از معیار های عنوان شده در الگوریتم پیشنهادی موجب بهبود عملکرد شبکه نسبت به پروتکل BAT، پروتکل NODIC و استاندارد IEEE802.15.4 می شود.

    کلیدواژگان: شبکه حسگر بی سیم، پروتکل IEEE802.15.4، الگوریتم خفاش، چاهک متحرک، انرژی مصرفی
|
  • MohammadPouya Akbarpour*, Keyhan Khamforoosh, Vafa Maihami Pages 2-21

    The time consumption in solving computationally heavy problems has always been a concern for computer programmers. Due to simplicity of its implementation, the PSO (Particle Swarm Optimization) is a suitable meta-heuristic algorithm for solving computationally heavy problems. However, despite the simplicity, the algorithm is inefficient for solving real computationally heavy problems but the presence of local interactions between particles has made this algorithm suitable for parallelization. On the other hand, by the invention of GPU (Graphical Processor Unit) and introducing the CUDA architecture as a GPU in the NVIDIA graphical processor, fundamental changes has been made in solving this type of problems. Despite all the research done in the field of implementing the algorithms through GPUs, some aspects of parallelization have not been addressed for suitable speedup and efficiency on NVIDIA GPUs. By considering the Geforce GT 525M, which is a relatively weak GPU, this paper tries to achieve the maximum speedup of the algorithm by implementing on this GPU. This experience led to reaching the acceptable efficiency on other GPUs. To reach the achievement, the multi-kernel model was used. The results show the speedup of 15.98 in solving the Rastrigin function.

    Keywords: Parallel Algorithm, PSO, GPU Computing, CUDA, Fermi, HPC
  • Seyed Majid Shafaei*, Babak Vaziri, Seyed Moostafa Shafaei Pages 22-37

    A real-time data warehouse is a collection of recent and hierarchical data that is used for managers’ decision-making by creating online analytical queries. The volume of data collected from data sources and entered into the real-time data warehouse is constantly increasing. Moreover, as the volume of input data to the real time data warehouse increases, the interference between online loading operations and online analytical processing increases. These two stated challenges have become the most important issues regarding real time data warehouse. In this article, a method is presented to improve the analytical queries response time in the real time data warehouse architecture using materialized views concatenation. This process takes place by: (1) storing the results of performed queries in each real time section, (2) transferring the results to the next section when transferring data to the section. Each real time section contains data of its previous section, which have been transferred in several stages. As a result, the calculated results of the queries are also transmitted by transferring data, and consequently, for achieving desired outcome, the previously calculated results can be combined without the need to run the queries again. The proposed method has reduced both analytical queries response time and data entry interference caused by the simultaneous and long-term execution of queries. This study faces two challenges: (1) applying the proposed method to a small amount of data in the real time section and (2) the changes in the proposed method for applying to big data.

    Keywords: Real-time data warehouse, Online Analytical processing, Partitioning, Materialized view, Data storage
  • Majid Mohammadpour, Behrooz Minaei, Hamid Parvin* Pages 38-65

    The SSPCO (See-See Particle Chicks Optimization) is a type of swarm intelligence algorithm derived from the behavior of See-See Partridge. Although efficiency of this algorithm has been proven for solving static optimization problems, it has not yet been tested to solve dynamic optimization problems. Due to the nature of NP-Hard dynamic problems, this algorithm alone is not able to solve such optimization problems. Therefore, to enable the algorithm to optimally track the variable in these problems, it is necessary to be provided solutions with this algorithm so that can increase the performance of this algorithm for dynamic environments. In this paper, two solutions for combining SSPCO are presented: (1) the multi-swarm method and (2) memory with Gaussian density estimation. The problem with most multi-swarm methods is that as the population increases uncontrollably, the speed and efficiency of the algorithm gradually decreases. The multi-swarm methods presented in this paper is adapted to the problem space, and whenever there is a need to increase the population, a population is created adaptively, and this reduces the problems of previous methods. One of the issues that is being addressed to solve uncertainty problems is prediction of near future using data of the near past. In this article, to preserve past data a new memory called Gaussian density estimation memory is used. This memory fixes standard memory defects and improves the performance of the proposed algorithm. To evaluate the efficiency of the proposed method, the well-known moving peak benchmark function, which simulates behavior of dynamic problems, is used. The proposed algorithm is compared with the 10 most popular dynamic optimization algorithms. According to the experimental results, the proposed method reduces offline error to a great extent compared to other methods and the error produced by the proposed method is very small.

    Keywords: Moving-Peak-Benchmark, Dynamic Optimization, Offline Error, SSPCO algorithm, Moving Peaks Benchmark, Density Estimation Memory, Clustering
  • Sajad Esfandyari*, Vahid Rafe Pages 66-79

    Up to now, several useful algorithms have been proposed to generate covering array, which is one of the branches of combinatorial testing. The main challenge in generating such arrays is generation of the arrays with a minimum number of test cases (for efficiency) at a proper time (for performance), for large systems. Covering array generation strategies are often divided into two general categories: computational and meta-heuristic. Computational strategies usually benefit high performance but have poor results in terms of efficiency. On the other hand, meta-heuristic strategies enjoy good efficiency but suffer low performance. Among the available strategies, the DPSO strategy generates the best results in terms of efficiency, but it does not benefit high performance; in contrast the GS strategy benefits good performance but has not good efficiency. Generally, there is no strategy that is good in terms of both efficiency and performance. In this paper, we try to produce an appropriate test suite of high efficiency and performance using PSO. A simple and effective minimizer function has also been used to increase the efficiency. The evaluation results show that the proposed solution has desirable outcomes in terms of efficiency and performance.

    Keywords: Combinatorial testing, Test suit generation, Covering array, PSO
  • Mostafa Ghobaei Arani*, Fatemeh Mahdi Babaei Pages 80-101

    Nowadays, processing large-media healthcare data in the cloud has become an effective way of satisfying the medical userschr('39') QoS (quality of service) demands. Providing healthcare for the community is a complex activity that relies heavily on information processing. Such processing can be very costly for organizations. However, processing healthcare data in cloud has become an effective solution to meet QoS demands of health users. In this paper, a fuzzy-based solution is presented for determining the optimal cloud using resource prediction technique. Besides, to make balance during the processing of tasks, based on fuzzy selector the virtual machine (VM) migration technique is used to migrate a VM from an overload server to an underload one. The proposed framework consists of two parts, local and global. To deliver the application to the global part, the local part must first be checked. If it is not suitable, the request will be delivered to the global part; indeed, the proposed framework works in a hierarchical manner. At first, a list of received requests is created and then using the proposed solution, the amount of available resources is estimated based on which the requested resources are allocated for processing. We used the Cloudsim toolkit to evaluate the proposed solution under various parameters and results have been compared with those of FAHP and ICA-K-Means algorithms. Compared to FAHP, the simulation results show that the proposed solution benefits from a 10% cost reduction and and a 12% reduction in cost compared to ICA-K-Means. Moreover, compared to FAHP and ICA-K-Means, the proposed method enjoys a reduction in number of rejected requests and an increase of 8% and 7% performance compared to the FAHP and ICA-K-Means, respectively.

    Keywords: Resource Allocation, Cloud Computing, Cloud Federation, Quality of Service, Fuzzy Selector, Healthcare Data
  • Shayesteh Tabatabaei* Pages 102-115

    Wireless sensor networks (WSNs) consist of sensor nodes with limited energy. Energy efficiency is an important issue in WSNs as the sensor nodes are deployed in rugged and non-care areas and consume a lot of energy to send data to the central station or sink if they want to communicate directly with the sink. Recently, the IEEE 802.15.4 protocol is employed as a low-power, low-cost, and low rate communication standard for WSNs, which ensures real-time applications via Guaranteed Time Slot (GTS). Accordingly, in this paper, a new protocol energy efficient bat algorithm and a mobile sink are presented. It can choose the optimal route based on: (1) distance of a sensor node to sink, (2), bat loudness, and (3) energy level of its battery. Using the OPNET simulator version 11.5, the proposed method was simulated by bat and NODIC protocols, and IEEE 802.15.4 and the results were considered in terms of energy consumption, end to end delay, signal to noise ratio, the success probability of sending data to sink and rate of passing data. The results of the simulation showed the use of the above-mentioned parameters in the proposed method leads to the improvement of the network throughput against using the IEEE 802.15.4 protocol, Bat algorithm, and NODIC protocol.

    Keywords: Wireless Sensor Network, IEEE 802.15.4 protocol, Bat algorithm, Mobile sink, Energy consumption