VLSI CAD: Logic to Layout Lecture 012 SAT Part 1

[음악] 그래서 강의 4에서 우리는 우리의 탐구를 완료 할 것입니다 전산 부울 대수 (boolean algebra)를 사용하여 다른 훌륭한 클래스를 보여줄 것입니다

부울 객체를 데이터 구조 및 연산자로 다루는 메소드 지난 강연에서 우리는 바이너리 결정 다이어그램을 매우 강력한 것으로 보여주었습니다 정말 훌륭하고 유용한 작업 세트를 지원하는 데이터 구조 BDD에 대해 흥미로운 점은 부울 함수 대단하네요

하지만 많이 있습니다 내가 정말로 알아야 할 모든 엔지니어링 예제는 부울 함수를 만든다 1 출력이나 그럴 방법이 없다 부울 함수를 1로 만들고 그 놀라운 것은 그 것만으로 충분합니다

그러나 많은 엔지니어링 시나리오에서이 강좌에서 볼 수 있습니다 그건 사실이야 그리고이 강의에서, 강의 41에서, boolean이라고 불리는이 새로운 클래스의 메소드를 소개 할 것입니다 또는 만족성에 SAT가 많이 있기 때문에

짧게 BDD와 같은 짧은 토 그래서 우리는 SAT에 대해 이야기 할 것입니다 우리는이 소개 강의에서 이야기하려고합니다 우리가 효율적으로 SAT를 할 수 있도록하는 결합 표준 형태 그래서 몇 가지 용어로 시작하겠습니다

부울 (boolean)이라고 불리는 것을보고 있습니다 satisfiability 및 satisfiability 많은 음절이 있기 때문에, 그것은 정말 한입 거의 모두가 그것을 토, 토라고 부릅니다 짧은 그리고 이것은 정말로 당신이 원한다면, 부울 대수의 물리학

방정식을 쓰고 싶습니다 그것을 해결하십시오 그리고 그것을 해결하는 것이 무엇을 의미합니까? 그것은 저에게 함수의 표현을 일종의 제게 알려줄 것입니다 변수 x1 ~ xn의 함수 그리고 우리는 변수가 0과 1이되도록 변수를 할당하면 기능 1

그리고 그것이 정말로 의미하는 것입니다 부울 함수는 1을 만들면 만족됩니다 이제이 할당은 고유하지 않을 수도 있습니다 제비 뽑기와 제비 뽑기가있을 수 있었다 만족스러운 솔루션

우리가 할 수만 있다면 행복하게 될 것입니다 그들 중 하나를 찾으십시오 그러나 만족스러운 과제가 없다면 전혀, 우리는 우리의 기술이 그것을 증명할 것으로 기대합니다 즉, 결론적으로이 부울 함수를 1로 만드는 방법은 없습니다 그것을 만족시키고 그 정보를 우리에게 돌려 줄 수있는 방법이 없습니다

이제 BDD로 할 수있는 일이 많다는 것을 알게되었습니다 근본적으로 전체의 구조를 표현하기에 좋다 부울 함수 하지만 가장 효율적이지는 않습니다 기술, 당신이 원한다면 그것을 만족시켜야합니다

그래서 당신이 단지 그것을 풀기를 원한다면 그것이 가능할지를 결정해야합니다 1 개 또는 2 개를 만들지 만, satisfiability 기술은 더 쉽고, 더 빠르며, 문제의 더 큰 경우 그래서 정말 좋은 솔루션입니다 사물을 해결하기 위해 그래서 SAT는 여러분이 단지 만족스러운 과제를 찾거나 하나가 없다는 것을 증명하고 싶습니다

그래서, 그 예가 무엇입니까? 오, 그 중 하나를 보여 줬어 이것은 초기 계산 부울 대수에 대한 네트워크 복구 예제입니다 강의 그래서, 여러분이 어떤 것을 가질 수 있다고 가정 해보십시오 알려진 좋은 버전의 논리

부울 방정식을 옳은 일과 게이트 수준의 구현은 효과가 없습니다 저 그림이 상단에 있습니다 그리고 우리는 당신에게 이것을 매우 흥미롭게 보았습니다 용의자 논리 게이트를이 경우 4 대 1로 대체 할 수있는 아이디어 멀티플렉서가 2 입력 게이트 인 경우 우리는 d0 또는 d3을 넣지 않았습니다 그리고 우리가 말했지, 알았어

의심스러운 논리 네트워크를 가져 와서 게이트를 꺼내 의심스럽고 4 : 1 멀티플렉서로 바꾸고, 더 큰 기능을 만드십시오 이 새로운 변수는 그것과 관련이 있습니다 그것을 노어 게이트를 통해 넣으십시오 평등 게이트입니다

이 두 블록이 논리는 1을 만들고 있습니다 그리고이 새로운 기능을 원래 입력의 함수 및 멀티플렉서를 지정하는 새로운 변수 그리고 나서,이 불리언 함수가 모든 시간에 하나가되기를 바랍니다 가능한 입력 값 그리고 보편적으로 정량화하십시오 우리는이 기능을 만들었습니다

우리가 말한 것은 당신이 그것을 해결할 수 있다면, 그것은 말하자면 1과 같게 만들 수 있다면 부울 네트워크에 영향을 미칠 수 있습니다 수리 그래서 여기에 그것은 하나의 예가 있습니다 이 중 단지 시나리오의 종류를 해결하고 싶습니다 모든 abz에 대한 정량화 함수를 만들 수 있다고 가정하면, D 값을 얻기위한 SAT 지정? 그렇다면 네트워크를 복구 할 수 있습니다

반대로, SAT 솔버가 돌아와서 이봐 요 이 정량화 된 부울 표현식을 해결할 방법이 없습니다 네트워크 복구가 불가능합니다 여기에 아주 좋은 콘크리트가 있습니다 부울 방정식을 푸는 엔지니어링 지향 시나리오 내가 뭘하고 싶은지

글쎄요, 이것들에 대한 용어가 있습니다 흥미롭게도 이러한 것들을위한 표준 형식이 있습니다 A,이 솔루션을 추구하는 가장 편리한 형태 이것은 conjunctive normal form CNF라고 불리는 것입니다 그리고 놀라운 점은 당신이 이것을 알고 있다는 것입니다, 당신은 그 이름을 모른다는 것입니다

이것은 합계 형태의 산물입니다 각 개별 용어는 괄호는 참 또는 칭찬 형태의 변수이거나 또는 우리와 모두 함께 이제 네가 뭘 생각하는지 알 겠어 와우, 너 내가 대학 시절에 배웠을 때 배운 것 같아 학습 디지털 디자인

하지만, 대부분 기억 나는 대부분 I 제품 형태의 합계를 기억하십시오 알다시피, 나는 카르노 (Karnaugh)지도를 만들 거니까 나는 1을 동그라미로 표시하고 제품처럼 보이는이 친숙한 용어를 얻을 수 있습니다 그들 사이에 더하기 기호가 있습니다 그리고 나는 그들이 나를 배우게 만들었다 고 생각합니다

0을 원으로 그리는 방법, 그리고 함수를 나타낼 수도 있습니다 하지만 나는 0을 대변하고 있었고, 나는 반전해야했기 때문에 매우 복잡했습니다 모든 변수와 나는 방금 그것을 잊었다 고 생각했습니다 죄송합니다 여기 있습니다

돌아왔다 합계의 제품을 배울 이유가 있습니다 형태 그리고 솔직히, 제품을 배우는 이유 왜냐하면 그것은 합당성에 대한 올바른 표현이기 때문입니다 그러면 괄호 안에있는이 용어들은 각각 무엇이라고 불 립니까? 그리고 대답은 절이라고 지칭됩니다

좋아요, 그래서이 각각 괄호 안에있는 것을 절이라고합니다 그리고 절 중 하나에 나타나는 변수를 살펴보면 사실입니다 형태가 아니기 때문에 보완되지 않는 것은 긍정적 인 문자라고합니다 그리고 여러분이 그러한 변수들 중 하나를 보았을 때 그것이 보완되면, 그것은 음수 리터럴 이제 여기서 주목할 사항 중 하나는 이, 각도 굴곡 기호 이런 종류

이것은 아닙니다 권리? 그래서 이것은 c bar 또는 c라고 말하는 것과 같습니다 초기 이것은 수학 논리의 종류입니다 부정에 대한 표기법

그리고이 재료는 50 년 전 우주의 수학 논리 측면 문학은 이와 같은 것들로 가득 차 있습니다 그래서 저는 여러분을 그렇게 유지할 것입니다 여러분은 그것이 어떻게 생겼는지에 대해 약간의 감각을 가지고 있습니다 왜 CNF가 유용합니까? 이봐 요, 만약 당신이 절은 0으로 평가하여 전체 수식이 0인지 여부를 확인합니다

이봐, 그들은 모두 그 안에있어 너는 1을 만들고 싶다 0 일때는 더 좋았습니다 만족스럽지는 않지만 물론 만족시키고 싶다면 모든 조항을 동일하게 만드십시오 1, 알다시피, 그것은 아마도 어려운 부분 일 것입니다 그래서 CNF 형식은 합계 형식의 표준 제품입니다

실제로 보았던 것입니다 전에 한 가지 더 많은 용어 및 할당 할당은 일부 사용자에게는 값을 제공하지만 그렇지 않은 사용자에게는 값을 제공합니다 반드시 모든 변수가 필요합니다

그리고 다른 용어는 꽤 똑바르다 앞으로 바로 여기 과제를 완료하고 모든 학생들에게 가치를 할당합니다 변수, 부분 할당은 일부 변수에 값을 할당합니다 그리고 과제는 조항 및 조항의 상태를 평가할 수 있음을 의미합니다

무심한 종류의 상태 일 수 있습니다 따라서 임의적 인 결정 만 내릴 수 있습니다 A는 0, b는 1이지만 c와 d는 지정되지 않습니다 그리고 몇 가지 질문을하고 조금만 보아라 전문 용어의 따라서, a가 0이고 b가 1이면, 첫 번째 절 a plus b가 0이 될 것입니다

또한 0으로 변하고이 전체 절은 0으로 평가되고 이 용어는이 절이 상충된다는 것입니다 왜 상충됩니까? 우리의 만족 목표와 충돌합니다 boolean 방정식 우리는 일종의, 우리가 할 수있는 일종의 희망입니다 이 phi 함수를 a1로 만드는 방법을 찾으십시오

절이 0으로 평가되면 그 목표와 충돌하고 우리는 그것이 상충된다고 말합니다 자, 다음 조항은 어떨까요? 플러스 b가 아니라 플러스 c 음, a가 1로 바뀔 것입니다 그리고 b는 0이 될 것입니다 그리고 더 이상 알 필요가 없습니다

이 절은 실제로 1입니다 그리고이 조항은 만족 스럽습니다 큰 놀라움은 없습니다 이 절은 1이므로 만족합니다 다음 절인 플러스 C 플러스는 어떨까요? 디? 글쎄, a는 0이고 나는 모른다

아무것도 더 우리가 솔직히 말해서 절이 해결되지 않았다는 것입니다 나는 그것이 가는지 알기에 충분하지 않다 0이되고 갈등이되고 나는 그것을 1로 만들고 그것을 말하기에 충분하지 않습니다 만족

그래서 나는 모른다 해결되지 않았다 마지막 하나는 a가 1이 아니고 b는 0이 아니며이 값은 0이 될 것입니다 절도 만족합니다 그래서, 그것들은 우리가 할 수있는 것들입니다

부울 (boolean) 방정식을 만족시키는 우리의 목표와 상충되는 부분에 대해 말하면, 만족 스럽습니다 1이나 이봐, 잘 모르겠다 해결되지 않았다 이런 것들을 어떻게 해결합니까? 음, 재귀 적으로 바라기를 당신은이 시점에서 놀랄만하지 않습니다

이것은 VLSI CAD 우주에서 반복해서 볼 수있는 패턴이 될 것입니다 정말 거대한 복잡한 문제가있어 해결 방법을 모릅니다 그것, 어쩌면 당신은 모든 조각에 작은 조각으로 그것을 나눌 수 있고 다시 함께 대답한다 그래서 저는 약간의 방법을 보여 드리겠습니다 재귀는 다음 슬라이드에서 작동합니다

그러나 재귀에는 두 가지 큰 아이디어가 있습니다 첫번째 결정은 결정이고 어떤 결정 수단이 보이는가, 때때로, 당신은 단지 변수를 선택하고 값을 지정하십시오 일종의 일이지만 목표는 변수에 값을 할당하면 CNF 수식을 단순화 할 수 있습니다 어쩌면 당신은 뭔가를 배울 수있을 것입니다 아마 그것은 만족 스럽습니다

어쩌면 충돌 일 수 있으며 나쁜 생각이고 실행을 취소해야합니다 기본 아이디어는 당신이 무언가를 임의로 결정한 다음 CNF 형식이 어떻게 단순화되는지, 그리고 여러분이 알 수 있든 없든 그것을 해결할 수 있는지에 대한 정보를 제공합니다 솔직히 더 관심있는 부분은 공제 부분입니다 그리고 공제에서, 당신은 새로 단순화 된 절을보고 계속해서 반복적으로 단순화하십시오 조항의 구조에 따라 귀하는 다른 값들이 다른 변수들에 할당되어야한다고 추론 할 수있다

그리고 이것은 부울의 만족스러운 부분의 멋진 부분입니다 임의로 몇 가지 변수 만 결정한 경우에도 다른 변수는 특정 값을 가져야 할 수도 있습니다 그렇지 않으면, 만족은 불가능합니다 그리고 그것은 정말로 가슴으로 밝혀졌습니다 부울 만족 성의 그래서 아무것도 할 때까지이 일을 계속합니다

단순화 한 다음 만족시킬 수 있습니다 그리고 그렇지 않다면 다시 돌아와 결정해야합니다 계속, 당신은 이것을 계속 추구합니다 이게 뭐야? 글쎄, 여기 결정 부분은 부울 방정식입니다 X 플러스 y 플러스 z 플러스 x 플러스 y

y 플러스 z가 아니라 x 플러스 y 플러스 z 없습니다 여기서 몇 가지 진전을 시도하겠습니다 그래서 우리는 x가 1이라고 결정할 것입니다 그럼 왼쪽 상자에서 저는 첫 번째 절에 대해 하나를 얻습니다 두 번째 절

세 번째 절에는 y와 z가 없습니다 y가 아니라 z가 아닙니다 그리고 그것은 나에게 여전히 복잡하다 아무것도 그래서 왜 그것의 1과 무슨 일이 일어나는 지 알기 만하면 나는 조금은 알고있다

복잡도 1 z, z 막대 이제이 시점에서 생각하고있을 것입니다 이봐, 우리는 일주일 내내 이진에 대해 배우는 것만 큼 많이하지 않았다 의사 결정도? 알다시피, 그것은 z와 같지 않습니다 z-bar는 정말 복잡한 기능, 나는 그것을 대표 할 수 없었습니다

a 0? 그리고 대답은 잘 알고 있습니다 예, 개념적으로 그렇습니다 그러나 실제로는 아니오, 왜냐하면 우리가 해결하려고하는 부울적 인 SAT 수식은 너무 거대합니다 이 검색 노드마다 BDD를 작성할 시간이 없어도됩니다 실제로 매우 다른 매우 가벼운 기술을 사용해야합니다

가서 질문하고 대답하십시오 우리를 위해서, 당신은 아직도 이것에 대답 할 수 없습니다 문제 이게 1인가요? 예 혹은 아니오 아니, 대답 할 수 없어

그래서 저는 더 멀리 가서 z를 0으로 지정해야합니다 그러면 여러분도 알 수 있습니다 그러면 저는 할 수 있습니다 실제로이 일이 만족스럽지 못하다고 말합니다 그래서 저는 다시 돌아가서 z를 다른 값으로 만들어 보겠습니다

그리고 여전히 만족스럽지 않다는 것을 알게 될 것입니다 다시 돌아가서 y를 1로 바꾸고 y를 0으로 만들면 다시 발견하십시오, 만족스럽지 않습니다 다시 돌아가 x가 1과 같은 결정을 취소합니다 결정 x는 0과 같아요 오, 이런, 복잡해

거기에서 아무 것도 할 수 없으므로 z를 1로 설정하기로 결정할 것입니다 그것을 만족시켰다 그래서 나는 끝났어 그리고 나머지 트리를 검색 할 필요가 없다는 것을 알게 될 것입니다 불린 satisfiability는 이것 같이 작동한다

나에게 만족스러운 임무를 찾아라 일단 찾으면 나에게 줘 나는 행복한 사람이다 만족할만한 과제가 없다면 실제로 검색해야합니다 영리한 방법으로 모든 것이 끝나고 해결책으로 돌아갑니다

미안하지만, 너는 이것을 만족시킬 수 없다 그래서, 아시다시피, 큰 질문은, 어떻게할까요? 당신은 많은 변수들을 알고 있기 때문에 당신은 이것을 빨리합니다 많은 일과 많은 일이 될 것입니다 그러니 다음에 조금 이야기하게하십시오 우리가 이것을 어떻게 풀어 냈는지 그리고 그런 종류의 것을 배우는 강의 알고리즘 적으로 흥미로운 부울 만족의 핵심

이것이 우리가 다음 강연에서 할 일입니다