首页 | 本学科首页   官方微博 | 高级检索  
     检索      


2-satisfiability and diagnosing faulty processors in massively parallel computing systems
Authors:Ansuman Bagchi  Brigitte Servatius  Weigeng Shi
Institution:

a Mathematical Sciences Department, Worcester Polytechnic Institute, 100 Institute Road, Worcester, MA 01609, USA

b Thinking Machines Corporation, 245 First Street, Cambridge, MA 02142, USA

Abstract:A fault diagnosis model for multiprocessor computers is proposed. Under normal operating mode each processor executes its own data. When an error occurs, the system is switched to the diagnostic mode. Previous input data for each processor is shifted to a different unit, to obtain a set of comparison results. We show that analysis of the test data to diagnose or locate faulty processors is equivalent to a 2-satisfiability problem. Under the assumption that discrepancy in a comparison result occurs if and only if at least one of the processors (being compared) is faulty, we prove that all the faulty processors can be diagnosed in O(n2) time, where n denotes the number of processors in the system.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号