检索结果-内蒙古大学图书馆

Computational challenges in bounded model checking

International Journal on Software Tools for Technology Transfer 2005年第2期7卷 174-183页

作者： Clarke, Edmund Kroening, Daniel Ouaknine, Joël Strichman, Ofer Computer Science Department Carnegie Mellon University Pittsburgh PA United States Department of Computer Science ETH Zudie rich Zürich Switzerland Oxford University Computing Laboratory Oxford United Kingdom Information Systems Engineering Faculty of Industrial Engineering Technion Haifa Israel

We describe several observations regarding the completeness and the complexity of bounded model checking and propose techniques to solve some of the associated computational challenges. We begin by defining the completeness threshold (Cτ problem: for every finite model M and an LTL property there exists a number Cτ such that if there is no counterexample to in M of length Cτ or less, then M. Finding this number, if it is sufficiently small, offers a practical method for making bounded model checking complete. We describe how to compute an overapproximation to Cτ for a general LTL property using Büchi automata, following the Vardi-Wolper LTL model checking framework. This computation is based on finding the initialized diameter and initialized recurrence-diameter (the longest loop-free path from an initial state) of the product automaton. We show a method for finding a recurrence diameter with a formula of size O(klogk) (or O(k(logk)²) in practice), where k is the attempted depth, which is an improvement compared to the previously known method that requires a formula of size in O(k²). Based on the value of Cτ, we prove that the complexity of standard SAT-based BMC is doubly exponential and that, consequently, there is a complexity gap of an exponent between this procedure and standard LTL model checking. We discuss ways to bridge this gap. © Springer-Verlag 2005.

关键词： Bonded-Model-checking Completeness-Threshold Complexity

来源：评论

学校读者我要写书评

暂无评论

Appointments for 2005-2006 term

引用

IEEE Transactions on Very Large Scale Integration (VLSI) systems 2005年第7期13卷 773-782页

作者： Ranganathan, Nagarajan Agrawal, Vishwani D. Chakradhar, Srimat T. Chakrabarty, Krishnendu Courtois, Bernard DeMara, Ronald Hu, Xiaobo Sharon Ismail, Yehea I. Jha, Niraj K. John, Lizy Kurian Ker, Ming-Dou Koren, Israel Liu, Bin-Da Marculescu, Diana Marculescu, Radu Narayanan, Vijaykrishnan Nassif, Sani R. Nowick, Steven M. Sapatnekar, Sachin S. Sherlekar, Sunil Sylvester, Dennis Vemuri, Ranga Pham, Michael Department of Computer Science and Engineering University of South Florida Tampa FL 33620 United States Department of Computer Science and Engineering Nanomaterials and Nanomanufacturing Research Center University of South Florida Tampa United States IEEE United States Systems United States Department of Electrical and Computer Engineering Rutgers University New Brunswick NJ United States IETE India ACM NEC Laboratories America Inc. Princeton NJ United States Duke University Durham NC United States ACM SIGDA Sigma Xi United States Laboratory of Techniques of Informatics and Microelectronics for Computer Architectecture ASME IMAPS IEEE Computer Society University of Central Florida Orlando United States Computer Engineering Program SEECS Department of Computer Science and Engineering University of Notre Dame Notre Dame IN United States Northwestern University Evanston IL United States Department of Electrical Engineering Princeton University Princeton NJ United States Association for Computing Machinery Austin United States UT Austin Engineering Foundation United States Department of Electronics Engineering National Chiao-Tung University Taiwan Department of Electrical and Computer Engineering University of Massachusetts Amherst United States Department of Electrical Engineering Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh PA United States Electrical and Computer Engineering Faculty Carnegie Mellon University Pittsburgh PA United States Computer Science and Engineering Department Pennsylvania State University University Park United States IBM Austin Research Laboratory Austin TX United States Columbia University New York NY United States Department of Electrical and Computer Engineering University of Minnesota Minneapolis United States Tata Consultancy Services Centre of Excellence for Embedded Systems India Department of Electrical Engineering IIT Bombay India Department of Electrical Engineering Uni

No abstract available

关键词：

来源：评论

学校读者我要写书评

暂无评论

Service Level Agreement based Allocation of Cluster Resources: Handling Penalty to Enhance Utility

Service Level Agreement based Allocation of Cluster Resource...

引用

IEEE International Conference on Cluster computing

作者： Chee Shin Yeo Rajkumar Buyya Grid Computing and Distributed Systems Laboratory Department of Computer Science and Software Engineering University of Melbourne VIC Australia

Jobs submitted into a cluster have varying requirements depending on user-specific needs and expectations. Therefore, in utility-driven cluster computing, cluster resource management systems (RMSs) need to be aware of these requirements in order to allocate resources effectively. Service level agreements (SLAs) can be used to differentiate different value of jobs as they define service conditions that the cluster RMS agrees to provide for each different job. The SLA acts as a contract between a user and the cluster whereby the user is entitled to compensation whenever the cluster RMS fails to deliver the required service. In this paper, we present a proportional share allocation technique called LibraSLA that takes into account the utility of accepting new jobs into the cluster based on their SLA. We study how LibraSLA performs with respect to several SLA requirements that include: (i) deadline type whether the job can be delayed, (ii) deadline when the job needs to be finished, (iii) budget to be spent for finishing the job, and (iv) penalty rate for compensating the user for failure to meet the deadline

关键词： Resource management Grid computing Quality of service Delay Finishing Admission control Laboratories computer science Software engineering Contracts

来源：评论

学校读者我要写书评

暂无评论

Critical-path and priority based algorithms for scheduling workflows with parameter sweep tasks on global grids

Critical-path and priority based algorithms for scheduling w...

引用

International Symposium on computer Architecture and High Performance computing (SBAC-PAD)

作者： Tianchi Ma R. Buyya Grid Computing and Distributed Systems (GRIDS) Laboratory Department of Computer Science and Software Engineering University of Melbourne Australia

Parameter-sweep has been widely adopted in large numbers of scientific applications. Parameter-sweep features need to be incorporated into grid workflows so as to increase the scale and scope of such applications. New scheduling mechanisms and algorithms are required to provide optimized policy for resource allocation and task arrangement in such a case. This paper addresses scheduling sequential parameter-sweep tasks in a fine-grained manner. The optimization is produced by pipelining the subtasks and dispatching each of them onto well-selected resources. Two types of scheduling algorithms are discussed and customized to adapt the characteristics of parameter-sweep, as well as their effectiveness has been compared under multifarious scenarios.

关键词： Scheduling algorithm Application software Sensor arrays Grid computing Filtering Data visualization Processor scheduling Resource management Laboratories computer science

来源：评论

学校读者我要写书评

暂无评论

Cost-based scheduling for data-intensive applications on global grids 05

Cost-based scheduling for data-intensive applications on glo...

引用

International Symposium on High Performance Distributed computing

作者： S. Venugopal R. Buyya Grid Computing and Distributed Systems (GRIDS) Laboratory Department of Computer Science and Software Engineering University of Melbourne Australia

We present an algorithm for scheduling distributed data intensive bag-of-task applications on data grids that have costs associated with requesting, transferring and processing datasets. We evaluate the algorithm on a... 详细信息

ISBN: (纸本)9780780390379

关键词： Processor scheduling Costs Grid computing Application software Physics computer networks Laboratories computer science Software engineering Testing

来源：评论

学校读者我要写书评

暂无评论

A time optimization algorithm for scheduling bag-of-task applications in auction-based proportional share systems

A time optimization algorithm for scheduling bag-of-task app...

引用

International Symposium on computer Architecture and High Performance computing (SBAC-PAD)

作者： A. Sulistio R. Buyya Grid Computing and Distributed Systems (GRIDS) Laboratory Department of Computer Science and Software Engineering University of Melbourne Carlton VIC Australia

Grid and peer-to-peer (P2P) network technologies enable aggregation of distributed resources for solving large-scale and computationally-intensive applications. These technologies are well-suited for bag-of-tasks (BoT) applications, because each application consists of many parallel and independent tasks. With multiple users competing for the same resources, the key challenge is to finish a user application within a specified deadline. In this paper, we propose a time optimization algorithm that schedules a user application on auction-based resource allocation systems. These allocation systems, which are based on proportional share, allow users to bid higher in order to gain more resource shares. Therefore, this algorithm adjusts a user bid periodically on these systems in order to finish the application on time.

关键词： Scheduling algorithm Application software Resource management Peer to peer computing Processor scheduling Grid computing computer applications Large-scale systems computer networks Distributed computing

来源：评论

学校读者我要写书评

暂无评论

Cost-based scheduling of scientific workflow applications on utility grids

Cost-based scheduling of scientific workflow applications on...

引用

IEEE International Conference on e-science and Grid computing

作者： Jia Yu R. Buyya Chen Khong Tham Grid Computing and Distributed Systems Laboratory Department of Computer Science and Software Engineering University of Melbourne VIC Australia Department of Electrical and Computer Engineering National University of Singapore Singapore

Over the last few years, grid technologies have progressed towards a service-oriented paradigm that enables a new way of service provisioning based on utility computing models. Users consume these services based on their QoS (quality of service) requirements. In such "pay-per-use" grids, workflow execution cost must be considered during scheduling based on users' QoS constraints. In this paper, we propose a cost-based workflow scheduling algorithm that minimizes execution cost while meeting the deadline for delivering results. It can also adapt to the delays of service executions by rescheduling unexecuted tasks. We also attempt to optimally solve the task scheduling problem in branches with several sequential tasks by modeling the branch as a Markov decision process and using the value iteration method

关键词： Optimal scheduling Processor scheduling Scheduling algorithm Workflow management software Grid computing Quality of service Costs computer networks Time factors Delay

来源：评论

学校读者我要写书评

暂无评论

NIPPERS: network of interpolated PeERS for Web service discovery

NIPPERS: network of interpolated PeERS for Web service disco...

引用

International Conference on Information Technology: Coding and computing (ITCC)

作者： C. Makris E. Sakkopoulos S. Sioutas P. Triantafillou A. Tsakalidis B. Vassiliadis Computer Engineering & Informatics Department University of Patras Patras Greece Internet and Multimedia Technologies Research Unit RA Computer Technology Institute Patras Greece Computer Science Digital Systems & Media Computing Laboratory Hellenic Open University Patras Greece

Web services are becoming an important enabler of the semantic Web. Besides the need for a rich description mechanism, Web service information should be made available in an accessible way for machine processing. In this paper, we propose a new P2P based approach for Web services discovery. Peers that store Web services information, such as data item descriptions, are efficiently located using a scalable and robust data indexing structure for peer-to-peer data networks, NIPPERS. We present a theoretical analysis which shows that the communication cost of the query and update operations scale double-logarithmically with the number of NIPPERS nodes. Furthermore, we show that the network is robust with respect to failures fulfilling quality of Web services requirements.

关键词： Web services Peer to peer computing Robustness Costs Interpolation Tree data structures Web and internet services Multimedia systems Multimedia computing Informatics

来源：评论

学校读者我要写书评

暂无评论

Journal of Information science and engineering: Editorial notice

引用

Journal of Information science and engineering 2005年第5期21卷 i-ii页

作者： Lee, Der-Tsai Amato, Nancy M. Chang, Shih-Fu Chen, Homer H. Chen, Tsuhan Hsu, Tsan-Sheng Hwang, Jenq-Neng Kuo, Sy-Yen Kuo, Tei-Wei Li, Chung-Sheng Tokuyama, Takeshi Wing, Jeannette Wu, Tzong-Chen Yen, John Computer Science at Texas A and M University United States Parasol Laboratory United States IEEE Transactions on Parallel and Distributed Systems Computing Research Association's Committee on the Status of Women in Computing Research CRA-W's Distributed Mentor Program United States Department of Electrical Engineering Columbia University United States Lab. United States College of Electrical Engineering and Computer Science National Taiwan University Taiwan IEEE Transactions on Circuits and Systems for Video Technology IEEE Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh PA United States ACM ACM SIGACT IEEE Computer Society IICM Austria Research and Development of the Department Multimedia Signal Processing Technical Committee IEEE Signal Processing Society United States IEEE Transactions on Circuits and systems for Video Technology College of Electrical Engineering and Computer Science National Taiwan Ocean University Keelung Taiwan Department of Electrical Engineering National Taiwan University Taiwan Department of Computer Science and Information Engineering National Taiwan University Taipei Taiwan IEEE Technical Committee on Real-Time Systems Computer Science Division IBM T.J. Watson Research Center United States IBM Research Division Graduate School of Information Sciences Tohoku University Japan ACM IPSJ Mathematical Society of Japan Japan Department of Computer Science Computer Science Department Carnegie Mellon University United States National Academies of Science's Computer Science and Telecommunications Board United States Microsoft's Trustworthy Academic Advisory Board Intel Research Pittsburgh's Advisory Board United States Dartmouth's Institute for Security Technology Studies Advisory Committee Canada Sloan Research Fellowships Program Committee United States ACM Taiwan China Information Sciences and Technology Pennsylvania State University United States Laboratory for Intelligent Agents Penn State's School of Info

No abstract available

关键词：

来源：评论

学校读者我要写书评

暂无评论

A market-based scheduler for JXTA-based peer-to-peer computing system

A market-based scheduler for JXTA-based peer-to-peer computi...

引用

International Conference on Computational science and its Applications, ICCSA 2004

作者： Ping, Tan Tien Sodhy, Gian Chand Yong, Chan Huah Haron, Fazilah Buyya, Rajkumar School of Computer Science Universiti Sains Malaysia Penang11800 Malaysia Grid Computing and Distributed Systems Laboratory Department of Computer Science and Software Engineering University of Melbourne Australia

ISBN: (纸本)3540220607

Peer-to-Peer (P2P) computing is said to be the next wave of computing after client-server and web-based computing. It provides an opportunity to harness a lot of idle peer-resources such as desktop computers across the Internet, for solving large-scale computing applications. Each peer is autonomous and it needs incentive for sustained contribution of its resources to P2P applications. In addition, a flexible and efficient job scheduling is needed to harvest the idle computing power as cheaply and economically as possible. This paper introduces an economic based job scheduler for mapping jobs to resources in P2P computing environment. The scheduler has been implemented with the Compute Power Market (CPM) system developed using Sun JXTA P2P technology. Our scheduler can be configured depending on users’ quality of service requirements such as the deadline and budget constraints. Our scheduler follows a hierarchy scheme. The design allows multiple consumers and multiple providers to schedule and run jobs. To allow wider support for a wide variety of applications, the system is designed to allow easy ‘plug in’ of user applications. © Springer-Verlag Berlin Heidelberg 2004.

关键词： Personal computers

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：