APPLICATION OF THEORY OF HIERARCHICAL CELLULAR AUTOMATA ( CA ) FOR

TEST AND DIAGNOSIS OF MICROPROCESSORS
 

A RESEARCH PROJECT PROPOSAL

SUBMITTED TO

INTEL CORPORATION
SANTA CLARA CALIFORNIA USA

BY

PROF. P PAL CHAUDHURI ( CHIEF INVESTIGATOR )
DIRECTOR, SCHOOL OF INFORMATION TECHNOLOGY
BENGAL ENGINEERING COLLEGE ( DEEMED UNIVERSITY )
SIBPUR HOWRAH WEST- BENGAL
INDIA 711103

AND

DR. S SUR KOLAY ( CO-INVESTIGATOR )
INDIAN STATISTICAL INSTITUTE , CALCUTTA
 
 

EXECUTIVE SUMMARY - SALIENT FEATURES OF THE PROPOSAL

I BACKGROUND

1. SIGNIFICANTAMOUNT OFRESEARCH HAVEBEEN DONEAT IITKHARAGPUR

AND BENGALENGINEERING COLLEGE( DEEMED UNIVERSITY)INTHE FIELD

OF THEORYAND APPLICATIONOF CELLAUTOMATA FORTESTINGVLSI

CIRCUITS.

2. SOME OF THE RESULTS OF THIS RESEARCH WORK HAVE BEEN REPORTED IN

THE BOOK AUTHORED BY P PAL CHAUDHURI AND HIS RESEARCH STUDENTS

" ADDITIVE CELLULAR AUTOMATA THEORY AND APPLICATIONS VOLUME 1 "

IEEE COMPUTER SOCIETY PRESS PUBLICATION, 1997. SUBSEQUENTLY, DURING

99. THE THEORY OF HIERARCHICAL CA HAS BEEN DEVELOPED AND

3. IN THE ABOVE BACKGROUND THE CURRENT RESEARCH PROJECT PROPOSAL

SPECIFICALLY TARGETS :
 
 

APPLICATION OF HIERARCHICAL CELLULAR AUTOMATA (CA) THEORY

FOR TEST AND DIAGNOSIS OF THE SPECIFIC CLASS OF VLSI

CIRCUITS CONVENTIONALLY REFERRED TO AS MICROPROCESSORS.

HANDLING MICROPROCESSOR CIRCUITS DEMAND SPECIAL TREATMENT

THAT WOULD BE TOTALLY DIFFERENT FROM THAT EMPLOYED FOR

TESTING GENERAL VLSI CIRCUITS OR CORES.
 

II DELIVERABLES
 

1. FIRST YEAR :

A GENERAL METHODOLOGY FOR APPLICATION OF HIERARCHICAL CA

THEORY FOR TESTING AN EXPERIMENTAL MICROPROCESSOR CIRCUIT.

THE PROOF OF THE CONCEPT WILL BE DEMONSTRATED BY THE END OF

FIRST YEAR FOR STUCK-AT-FAULT MODEL.

2. SECOND YEAR

 

 
 
 
 
 
 

A GENARILISED CAD PACKAGE FOR TESTING A MICROPROCESSOR CIRCUIT

WITH INDICATION OF FAULT ( BOTH STUCK-AT AND DELAY FAULTS )

COVERAGE ALONG WITH AREA OVERHEAD AND PERFORMANCE PENALTY.

THE PACKAGE WILL PROVIDE ALTERNATIVE SOLUTIONS TO MEET THE

SPECIFIC REQUIREMENTS OF THE DESIGNERS IN TERMS OF TARGETED

FAULT COVERAGE AND OVERHEADS.
 
 
 
 
 
 
 
 
 
 

3. THIRD YEAR

NOTE : IF THE PROJECT IS INITIATED ON JANUARY 2000, THE

PROTOTYPE CAD PACKAGE WILL BE HANDED OVER TO INTEL

BY 2001 FOR EXPERIMENTATION ON REAL LIFE DESIGNS. BASED

ON FEEDBACK FROM INTEL DESIGNERS THE PACKAGE WILL BE

REFINED ON THE THIRD YEAR OF THE PROJECT - THE YEAR 2002.
 
 
 

III MODALITIES OF INTERACTION
 
 

FOR SUCCESSFUL IMPLEMENTATION OF THE PROJET IT IS DESIRABLE THAT :

THERE IS CONTINUOUS INTERACTION OF INTEL DESIGNERS WITH THE

RESEARCH TEAM WORKING UNDER PROF. P PAL CHAUDHURI AT BENGAL

ENGINEERING COLLEGE ( DEEMED UNIVERSITY ) THROUGH EMAIL, FAX,

TELECONFERENCE, AND ACROSS - THE - TABLE DISCUSSIONS WITH AN

AVERAGE FREQUENCE OF TWO/THREE TIMES IN A YEAR.
 
 

THIS MODALITY HAVE BEEN SUCCESSFULLY FOLLOWED IN RESPECT

OF THE FIRST RESEARCH PROJECT ( ON ASYNCHRONOUS CIRCUIT

TESTING ) SPONSORED BY INTEL IN NOV.,1997 AND ALSO FOR

RESEARCH PROJECTS FUNDED BY OTHER MULTINATIONAL COMPANIES

OF NORTH AMERICA TO PROF. P PAL CHAUDHURI AT BENGAL

ENGINEERING COLLEGE ( DEEMED UNIVERSITY ).
 
 
 

I INTRODUCTION
 
 

1.1 IN THE ERA OF DEEP SUB-MICROON TECHNOLOGY, THE EXISTING TEST

SOLUTIONS BUILT AROUND FULL/PARTIAL SCAN ( OR FUNCTIONAL TESTING )

WILL NOT BE COST EFFECTIVE FOR TESTING A LARGE SCALE

MICROPROCESSOR CIRCUIT.
 
 
 
 
 
 

THE ALTERNATIVE SCHEME OF BIST ( BUILT-IN-SELF-TEST ) METHODOLOGY IS

GENERAL METHODOLOGY FOR INSERTION OF BIST STRUCTURE IN A GENERAL

MICROPROCESSOR CIRCUIT. THE RESULTS REPORTED IN THE PUBLISHED

LITERATURE ARE MOSTLY AD -HOC IN NATURE.
 
 
 
 

1.4 IN THE ABOVE CONTEXT THIS PROJECT PROPOSAL HAS BEEN FORMULATED

TO SOLVE THE PROBLEM OF TESTING MICROPROCESSORS BASED ON THE

BACKGROUND PREPARATION REPORTED IN THE NEXT SECTION.
 
 
 

II BACKGROUND PREPARATION
 
 
 
 

2.1 SIGNIFACANT AMOUNT OF RESEARCH WORK IN THE FIELD OF CELLULAR

AUTOMATA ( CA ) HAVE BEEN CONDUCTED BY THE RESEARCH GROUP HEADED

BY PROF. P PAL CHAUDHURI AT INDIAN INSTITUTE OF TECHNOLOGY

KHARAGPUR INDIA DURING 1988 TO 1996 AND SUBSEQUENTLY AT

BENGAL ENGINEERING COLLEGE ( DEEMED UNIVERSITY ).

SOME OF THESE RESEARCH RESULTS ARE REPORTED IN THE BOOK ENTITLED

" ADDITIVE CELLULAR AUTOMATA THEORY AND APPLICATIONS VOL 1 "

IEEE COMPUTER SOCIETY PRESS PUBLICATION, 1997.

2.2 THE PROOF OF THE CA THEORY EMPLOYED AS A CABIST ( CA BASED BUILT-

IN-SELF-TEST) STRUCTURE FOR TESTING VLSI CIRCUITS HAVE BEEN

DEMONSTRATED IN MID 90’S ON BENCHMARK CIRCUITS AND ALSO ON SOME

INDUSTRIAL DESIGNS.
 
 
 
 

2.3 AS A VISITING FACULTY AT STRATEGIC CAD LAB ( SCL ) INTEL CORPORATION

PORTLAND , IN 1997 PROF. P PAL CHAUDHURI DEMONSTRATED THE

APPLICATION OF THE CABIST THEORY FOR TEST SOLUTION OF THE

EXPERIMENTAL ASYNCHRONOUS CIRCUIT - THE RAPPID CHIP DESIGNED BY

THE INTEL RESEARCH TEAM.
 
 
 

2.4 SINCE 1998 PROF. P PAL CHAUDHURI AND DR. SUSMITA SUR KOLAY HAVE

BEEN DEVELOPING A PACKAGE FOR

" ENHANCING TESTABILITY OF ASYNCHRONOUS CIRCUITS "

THROUGH INSERTION OF CABIST STRUCTURE IN AN ASYNCHRONOUS CIRCUIT.

THIS WORK IS BEING CARRIED OUT UNDER THE RESEARCH GRANT FUNDED

BY INTEL CORPORATION, USA FOR THREE YEARS ( 1998 – 2000 ).
 
 
 
 

2.3 THE WORK ON HIERARCHIAL CA STRUCTURE BUILT AROUND THE THEORY

OF EXTENSION FIELD WAS INITIATED AT IIT KHARAGPUR DURING 1995-96.

SUBSEQUENTLY, THE COMPLETE THEORY OF THE HIERARCHICAL CA

( REFERRED TO AS GF (2**P)**Q) CA ) HAVE BEEN DEVELOPED AT B E

COLLEGE (DEEMED UNIVERSITY) THROUGH TWO PH.D THESIS WORK.
 
 

2.4 THE THEORY DEVELOPED UNDER THE PH.D WORK AT B E COLLEGE ON

HIERARCHICAL CA ( AS REPORTED IN THE VLSI 2000 CONFERENCE PAPER )

HAS BEEN APPLIED FOR TESTING VLSI CIRCUITS.

WITH THE ABOVE BACKGROUND PREPARATION, THE THEORY

OF HIERARCHICAL CA WILL BE APPLIED FOR TEST SOLUTION OF

MICROPROCESSORS AS ELABORATED IN THE NEXT SECTION.
 
 

III THE PROJECT OUTLINE
 
 
 
 

3.1 A PROTOTYPE CAD PACKAGE ( NAMED AS A CABISTMP - CELLULAR

AUTOMATA based BUILT - IN - SELF - TEST for MICROPROCESSORS ) WILL

BE DEVELOPED UNDER THIS PROJECT.
 
 

3.2 THE INPUTS (OUTPUTS) TO (FROM) THE PACKAGE ARE :

1. INPUTS : HIERARCHICAL STRUCTURAL AND FUNCTIONAL

DESCRIPTION OF THE MICRPOPROCESSOR CIRCUIT AS

NETLIST OF GATES, AND A NETLIST OF RTL/

FUNCTIONAL MODULES.
 
 

2. OUTPUTS : BIST-ED MICROPROCESSOR WITH THE INDICATION OF

THE PERCENTAGE FAULT COVERAGE , AREA

OVERHEAD, AND PERFORMANCE PENALTY.
 
 

3.3 THE METHODOLOGY TO EMBED HIERARCHICAL CABIST STRUCTURE
 
 

1. BASED ON THE INPUT HIERARCHICAL FUNCTIONAL/STRUCTURAL

DESCRIPTION , THE CIRCUIT WILL BE FUNCTIONALY

PARTITIONED TO ARRIVE AT DIFFERENT ECONOMICALLY BIST

- ABLE MODULES. AN EFFICIENT FUNCTIONAL PARTITIONING

ALGORITHM WILL BE DEVELOPED SPICIFICALLY TO HANDLE

LARGE SCALE MICROPROCESSOR CIRCUITS.
 
 

2. CABIST STRUCTURE WILL BE DESIGNED FOR EACH MODULE

BASED ON THE THEORY DEVELOPED FOR ANALYSIS OF

THE HIERARCHICAL CA AND THE FUNCTIONALITY EMBEDED

IN THE MODULE.

3. A HIERARCHICAL CABIST STRUCTURE WILL BE FINALLY

DESIGNED WHILE COMBINING THE BIST STRUCTURES EMBEDED

FOR EACH MODULE.
 
 
 
 

SECOND YEAR

TESTING OF THE PACKAGE BY INTEL DESIGNERS ON REAL LIFE

4.3 THIRD YEAR

DELIVERABLES FROM BEC : THE REFINED PACKAGE BASED ON

THE FEEDBACK FROM INTEL

DESIGNERS.

DIAGNOSIS METHODOLGY FOR

DESIGN DEBUG AND SILICON DEBUG.
 
 

COMMITMENT FROM INTEL ; THOROUGH TESTING AND FEEDBACK

ALONG WITH CONTINUOUS

INTERACTION WITH THE BEC TEAM.
 
 
 
 
 

V THE BUDGET
 
 

(I) FUND OF US $ 50, 000 WILL BE RELEASED BY INTEL CORPORATION

IN THE BEGINNING OF EACH YEAR TO MEET THE PROJECT

EXPENSES FOR PURCHASE OF EQUIPMENTS , SALARY FOR THE

RESEARCH STAFFS/STUDENTS AND OTHER MISCELLENEOUS

HEADS.

TOTAL AMOUNT FOR THREE YEARS : $ 1 50, 000

NOTE : PROVISION SHOULD BE ALSO KEPT FOR THE FOLLOWING

EXPENSES -

(II) VISIT OF BEC TEAM MEMBERS TO INTEL SANTA CLARA OFFICE

FOR INTERACTION WITH INTEL DESIGNERS - TRAVEL AND

HOTEL EXPENSES - TWO VISITS PER YEAR FOR TWO PROJECT

STAFFS.

VI BIODATA OF INVESTIGATORS
 
 

BIODATA OF CHIEF INVESTIGATOR

ADDRESS : DEPARTMENT OF COMPUTER SCIENCE AND TECHNOLOGY

BENGAL ENGINEERING COLLEGE ( DEEMED UNIVERSITY )

SIBPUR, HOWRAH 711103

WEST-BENGAL, INDIA
 
 

EXPERIENCE :
 
 

PROFESSIONAL EXPERIENCE : IBM WORLD TRADE CORPN. ( 1963-75 )
 
 

TEACHING AND RESEARCH : IIT KHARAGPUR ( 1975 – 96 )

BENGAL ENGINEERING COLLEGE ( 1998 - )
 
 

VISITING FACULTY ( UNIVERSITY OF

ILLINOIS, URBANA CHAMPAINGE) - 1991,

AND INTEL RESEARCH LABS, PORTLAND ,

USA – 1997.
 
 
 
 
 
 
 
 
 
 
 
 

P 14

PUBLICATION : MORE THAN 100 RESEARCH PAPERS IN

INTERNATIONAL JOURNALS AND

CONFERENCE PROCEEDINGS.

TWO BOOKS - (1) THE BOOK ON

CELLULAR AUTOMATA PUBLISHED BY

IEEE COMPUTER SOCIETY PRESS, USA IN

MAJOR RESEARCH CONTRIBUTION :
 
 

DEVELOPED THE THEORY OF CELLULAR AUTOMATA AND ITS APPLICATIONS

IN DIVERSE FIELDS -

VLSI TESTING AND DESIGN, DESIGN OF ERROR CORRECTING CODES, DATA

ENCRYPTION, DATA COMPRESSION, MODELLING PHYSICAL SYSTEMS ETC.