매우 까다로운 데이터 경로 기능을 공식적으로 검증하는 다른 접근 방식입니다. Paul Cunningham(GM, Verification at Cadence), Raúl Camposano(실리콘 촉매, 기업가, 전 Synopsys CTO, 현 Silvaco CTO) 그리고 저는 연구 아이디어에 대한 시리즈를 계속하고 있습니다. 언제나처럼 피드백을 환영합니다. 올해는 검증 탐색에 주름을 추가할 계획입니다. 따라야 할 세부 사항!

혁신

이번 달의 선택은 부동 소수점 가산기의 다항식 형식 검증. 이 기사는 2023 DATE 컨퍼런스에 게재되었습니다. 저자는 독일 브레멘대학교 출신이다.

데이터 경로 요소 구현은 절대적으로 올바른 것으로 입증되어야 하며(악명 높은 Pentium 부동 소수점 버그 기억) 공식적인 증명이 필요합니다. 그러나 부동 소수점 요소에 대한 BDD 상태 그래프는 급속도로 폭발적인 반면, SAT 증명은 종종 경계가 있어 완전하지 않습니다.

오늘날 널리 사용되는 해결 방법은 C/C++ 참조 모델과 함께 동등성 검사를 사용하는 것입니다. 이는 매우 잘 작동하지만 물론 신뢰할 수 있는 참조에 의존합니다. 그러나 일부 용감한 사람들은 여전히 ​​BDD를 통해 길을 찾으려고 노력하고 있습니다. 이 저자들은 상태 그래프 폭발을 제한하기 위해 케이스 분할을 사용하여 지수적 복잡성에서 다항식 경계 복잡성으로 감소하는 방법을 제안합니다. 리뷰어들의 생각을 살펴보겠습니다!

바울의 견해

2024년에 시작되는 읽기 쉽고 컴팩트한 논문으로, 컴퓨터 과학의 고전적인 문제인 공식 검증에서 BDD 크기 폭발을 관리합니다.

이 논문의 주요 기여는 부동 소수점 가산기의 공식 검증에서 "케이스 분할"을 위한 새로운 방법입니다. 전통적으로 사례 분할은 BDD의 크기를 크게 늘리는 부울 변수를 선택하고 해당 변수가 참인 "사례"에 대해 하나, 해당 변수가 거짓인 경우에 대해 하나씩 두 개의 별도 형식 증명을 실행하는 것을 의미합니다. 두 증명이 모두 통과되면 해당 변수를 포함한 전체 BDD에 대한 전체 증명도 반드시 통과해야 함을 의미합니다. 물론 n 변수에 대한 케이스 분할은 2^n 케이스를 의미하므로 어디에서나 사용한다면 하나의 지수 폭발을 다른 것으로 교환하면 됩니다.

이 문서에서는 사례 분할이 개별 부울 변수에만 기반할 필요는 없다는 점을 관찰합니다. 문제를 철저하게 세분화하는 것은 유효합니다. 예를 들어, 밑 지수를 정규화하기 전에 밑의 선행 10 수에 대한 사례 분할이 수행될 수 있습니다. 즉, 밑의 선행 XNUMX XNUMX, 밑의 선행 XNUMX XNUMX개 등입니다. 정렬 이동 단계에서 다른 교활한 분할과 결합된 이 특정 분할 선택은 부동 소수점 덧셈에 대한 전체 증명이 복잡성의 지수 함수에서 다항식으로 바뀌는 마법 같은 절충안을 달성합니다. 이제 배정밀도 부동 소수점 덧셈 회로가 XNUMX초 만에 공식적으로 올바른 것으로 입증될 수 있습니다. 멋진!

라울의 견해

이 짧은 문서에서는 동등성 검사의 고전적인 문제인 BDD를 사용하는 부동 소수점 가산기의 공식 검증에서 크기 폭발 문제를 관리하는 새로운 접근 방식을 소개합니다. 전통적으로 이는 사례 분할, 즉 개별 부울 변수(0, 1)의 값을 기준으로 문제를 분할하는 방법으로 해결되었으며 분할된 변수의 수에 따라 복잡성이 기하급수적으로 증가합니다. 본 논문에서는 BDD를 구축할 때 크기가 폭발적으로 증가하는 지점에 대한 관찰을 바탕으로 세 가지 혁신적인 사례 분할 방법을 제안합니다. 이는 개별 부울 변수를 기반으로 하지 않으며 부동 소수점 가산기에 특정합니다(물론 P에 대한 일반적인 동등성 검사를 단순화하지 않습니다).

1. 정렬 이동 케이스 분할: 이 논문에서는 이동량 또는 지수 차이에 대한 분할을 제안하여 검증에 필요한 케이스 수를 크게 줄입니다.
2. 선행 0 케이스 분할: 정규화 전환 시 폭발을 해결하기 위해 이 논문에서는 덧셈 결과의 선행 0 수를 기반으로 케이스 생성을 제안합니다.
3. 비정규 숫자 및 반올림: 비정규 숫자는 발생할 수 있는 경우 단순화를 추가하여 처리됩니다. 반올림은 BDD 크기의 폭발을 유발하지 않습니다.

이러한 사례 분할을 전략적으로 선택함으로써 부동 소수점 추가에 대한 전체 증명 복잡성을 지수에서 다항식으로 줄일 수 있습니다. 결과적으로, 고전적인 기호 시뮬레이션에서는 10시간에 종료되는 이중 및 300중 정밀도 부동 소수점 추가 회로의 공식 검증이 이제 XNUMX-XNUMX초 안에 완료될 수 있습니다!

다음을 통해이 게시물 공유 :

• SEO 기반 콘텐츠 및 PR 배포. 오늘 증폭하십시오.
• PlatoData.Network 수직 생성 Ai. 자신에게 권한을 부여하십시오. 여기에서 액세스하십시오.
• PlatoAiStream. 웹3 인텔리전스. 지식 증폭. 여기에서 액세스하십시오.
• 플라톤ESG. 탄소, 클린테크, 에너지, 환경, 태양광, 폐기물 관리. 여기에서 액세스하십시오.
• PlatoHealth. 생명 공학 및 임상 시험 인텔리전스. 여기에서 액세스하십시오.
• 출처: https://semiwiki.com/eda/342214-bdd-based-formal-for-floating-point-innovation-in-verification/