VLSI CAD: Logic to Layout Lecture 010 BDD Sharing

여기서 우리는 강의 33에 있습니다

우리는 우리의 탐험을 계속하고 있습니다 전산 부울 논리합 및 이진 의사 결정 다이어그램 지금까지 우리는 당신의 모습을 보여주었습니다 부울 함수에 대한 BDD입니다 그러나 솔직히, 실제 세계에서 하나의 부울 출력을 조작하고 싶습니까? 권리? 실제 칩의 로직 블록을 아십니까? 많은 투입물과 많은 양의 출력물을 가지고 있습니다

우리는 많은 부울 방정식을 동시에 조작 할 수 있어야합니다 BDD가이를 자연스럽게 지원한다는 것이 밝혀졌습니다 사실 BDD에서 노드를 공유 할 수 있으므로 많은 다른 기능을 사용할 수 있습니다 BDD에서 노드의 동일한 생태계 그 중 하나가 실제로 보다 효율적인 BDD

그래서이 강의에서 우리는 공유를 통해 실제로 복잡한 세트를 표현할 수있는 몇 가지 예가 있습니다 한 세트의 BDD 노드를 가진 함수들 이제 우리가 어떻게 결정 다이어그램으로 시작하여 BDD를 줄입니다 적어도 개념적으로 루트에서 리프까지 전체 변수 순서를 요구하며, 그런 다음 BDD를 줄여 중복성이 없도록합니다 가장 작고, 가장 단단한 가능한 BDD

잠깐 얘기하자 당신이 할 수있는 흥미로운 것들 첫 번째로 할 수있는 일은 함수를 나타냅니다 그리고 무엇이든 부울 함수는 감소 된 주문형 BDD 그리고 표준 방식으로 그렇게 할 수 있습니다

그래서 멋진 일이 일어납니다 내가 너에게 말하면 내 변수 x1에서 xn은 0입니까? 권리? 어떻게 그것을 우리가 축소 된 BDD로 표현할 수 있을까요? 음, 정말로 하나의 옵션 만 있습니다 정확히 한 가지 옵션이 있습니다 그 이 함수가 0과 같으면 모두에게 가능한 입력이면, 0 노드에 대한 포인터 일뿐입니다

부울 함수가 1이면? 좋아, 그럼, 똑같은거야 일어날 것이다 Boolean 함수가 1이면, 단지 1 노드에 대한 포인터 여야합니다 그리고 나는 옆으로 갈거야 이 작은 텍스트 상자는 여기에 있고, 여기 상자에 말을 해봅시다

어떤 것 Reduced Ordered BDD에서 부울 함수는 실제로 표준 그래프 데이터의 루트 노드에 대한 포인터입니다 구조 따라서 BDD의 최상위 노드를 가리 킵니다 그런 다음 BDD를 내리고 그 값을 결정하는 방법입니다

함수를 사용합니다 f가 0이면 0 노드에 대한 포인터입니다 기간 다른 방법은 없습니다 사고

함수가 1이면 포인터입니다 1 노드로 다른 방법은 없습니다 감소 된 주문형 BDD는 정식입니다 대표하는 유일한 방법이 있습니다

모든 기능 그래서 이것은 아주 좋은 단순한 것입니다 반대로 함수가 x1, x2, dot, dot, dot, xn 변수 중 하나라면? 그리고 우리는 그 변수 중 하나를 선택합니다 그냥 x라고 부릅니다 그리고 우리는 함수가 x이고 다른 모든 변수를 무시한다고 말합니다

그러면 변수 노드를 얻게 될 것입니다 그리고 낮은 아동은 0 점을 가리킬 것입니다 그리고 높은 아이는 1 점을 가리킬 것입니다 그리고 함수 자체는 그 x 노드를 가리킬 것입니다 그래서 그것은 정말로 아주 좋은 단순한 종류의 것입니다

우리가 더 흥미로운 기능을 가지고 있다면, 약간의 복잡성 우리는 함수와 함수가 있다고 가정합시다 그것은 x1, x2, x3, x4의 4 가지 변수의 함수라는 것입니다 그리고 그 순서는 사실 x1, x2, x3, x4 순입니다 여기 왼쪽에는 단순한 함수가 있습니다

X1 + x2 및 x4 우리가 주목할 것은 흥미롭게도 충분히, x3이라고 표시된 정점은 존재하지 않을 것입니다 왜냐하면 x2 이후와 x4 이전이어야합니다 그러나이 특별한 함수는 x3에 의존하지 않으므로 x3이 존재하지 않습니다 많은 그래프가 공유됩니다

앞으로 더 많은 것을 이야기 할 것입니다 이 이야기에서 광범위하게 그리고 당신도 아시다시피, 함수는 실제로이 BDD의 최상위 노드 중 하나 또는 두 번째 포인트입니다 BDD는 실제로 변수를 정의하는 변수에 대한 포인터 일 뿐이므로 BDD 그래프 데이터 구조의 맨 위 그리고 당신이 볼 수있는 것은, 만약 당신이 이 BDD가 실제로 의미가 있다는 것을 조금 생각해보십시오

알고있다 예를 들어이 물건이 정말로 x1, x4 + x2 x4 그래서 제가 기대하는 것은 유일한 두 가지 방법입니다 이 기능을 1로 만들려면 첫 번째 학기를 1로 만들 필요가 있습니까? 아니면 2 학기를 1로 만들 필요가 있습니까? 권리? 첫 번째 용어를 1로 만드는 방법은 x1은 1이어야하고 x4는 1이어야한다고 말하는이 경로를 따라 가야합니다

두 번째 경로를 만드는 방법은이 경로를 따라 가야합니다 x2는 1이고 x4는 1입니다 따라서 실제로 작동합니다 홀수 패리티는보다 재미 있고 일종의 고밀도입니다 기능

홀수 패리티는 x1 배타적 또는 x2 배타적입니다 또는 x3 exclusive 또는 x4 그리고 그것을 의미하는 이상한 동등 함 입력 사이에 홀수의 1이있는 경우에만 1을 만듭니다 예를 들어, x1, x2, x3, x4라고 말하면됩니다 우리가 1, 1, 1 0이 있다고 상상해보십시오

이것이 작동하는지 봅시다 괜찮아 여기에 x1이 1입니다 여기 x2는 1입니다 여기 x3은 1입니다

여기에 x4는 0입니다 예, 1을 만듭니다 괜찮아 그래서 이것은 일종의 지그재그 타입입니다 앞뒤로 경로

이것은 매우 밀집된 방법으로 홀수 개의 대표 변수가 언제 신경 쓴다는 사실 가치 1을 가져라 내가 1로 갈 수있는 유일한 방법이다 짝수 개의 지그재그가있는 경로는 나를 0으로 만듭니다 그것은 매우 타이트한 표현입니다 매우 우아하고 컴팩트 한 제품입니다

대표 그리고 그것은 또 다른 아주 또 다른 것을 보여주고 있습니다 중요한 기술적 요점 그리고 그것은 일종의 것입니다 이 강의의 요점

모든 BDD 노드는 루트뿐만 아니라 모든 BDD 노드는 표준 방식으로 몇 가지 부울 함수를 나타냅니다 이제 x1을 조작하려고하기 때문에 왼쪽에 BDD를 만들 수 있습니다 x2와 x4를 더하면 좋을 것 같습니다 그러나 BDD 내의 모든 노드는 루트입니다 일부 하위 그래프의 그리고 그 중 하나 하나가 다른 기능

심지어 너의, 심지어 너를 원하지 않았다 그것을 만들려고하지 않았다, 그것은 단지 일어난다 권리? 그래서 예를 들어, 이것이 바로 f입니다 그리고 이것은 f입니다 맞습니다

x1 + x2 plus x 시간 x4 그거 대단 하네 내가 너에게 말한다면, 그 함수는 ag입니까? 그게 뭐야? 권리? 그리고 당신이 응시하는 것을 조금만 그 g는 x2 x4와 같습니다 그리고 그것은 당신에게 정말로 좋은 감각을 알리게합니다

유일한 방법은 1 노드에 도착할 수 있습니다 g에서 시작하여 x2는 1이고 x4는 1입니다 그래서 g는 x2 x4입니다 그게 단지 끝이라고 알고 있잖아 x2와 x4를 입력으로 사용합니다

우리가 살펴 본다면, 오른쪽의 BDD, 괜찮아? 그리고, 우리는 지금 당장이 말을합니다, 이것은 f입니다, 괜찮아? 그래서 f는 x1 exclusive 또는 x2와 같습니다 독점 또는 x3 독점 또는 x4 그리고 지금 나는 중간을 가르키 기 시작한다 그 노드와 같은 노드 있잖아, 내가 뭘 알아? 글쎄, 만약 당신이 하나의 노드가 실제로 함수의 근원 인 것을 보았다면 x3 배타적 또는 x4

권리? 1 노드로 갈 수있는 유일한 방법은 x3이 x4와 동의하지 않는 경우입니다 다른 값 그리고 반대로,이 쪽의 1, 오른쪽, 배타적 단어 BDD의 B의 오른쪽에있는 1은 x3 배타적도 아니다 x4 그리고 알림의 방법으로, 그것은 단지 그것의 출력에 인버터 버블과 배타적 또는 게이트 그리고 그것은 실제로 두 입력에 대한 균등 패리티 함수입니다

마찬가지로, x4 노드의 오른쪽에있는 노드가 실제로는 그냥 함수 x4 막대의 뿌리, 맞죠? 그리고 당신은 그것을 응시합니다 x4가 0이면 1을 얻습니다 그리고 x4가 1이면 0이됩니다 그건 x4가 아니야 이제 우리는 모든 노드 내부 BDD는 함수를 나타냅니다

그리고 우리는 이것을 일종의 다음 논리적 인 단계는 우리가이 사실에 유용한 것을 할 수 있다는 것입니다 여기에 더 흥미롭고 다소 현실적인 예가 있습니다 이제 4 비트 가산기를 고려해 보겠습니다 그래서 내가 너에게 보여줄 노란색 상자 왼쪽에 4 비트 덧셈기가있다 그것은 4 비트 숫자의 두 세트를 가지고 있습니다

입력 그것은 a3, a2, a1, a0을 가지고 있습니다 그것은 4 비트입니다 번호 그리고 그것은 b3, b2, b1, b0을 가지고 있습니다

그것은 또 다른 4입니다 비트 수 이 번호들을 함께 더합니다 그것은 합계, s3, s2, s1, s0을 산출합니다 하지만 나는 다른 것보다 신경 쓰지 않는다

최상위 비트, 합계의 상위 비트 그건 s3입니다 그리고 그것은 수행해야합니다 그리고 나는 여기서 완전성을 위해, 들어 가지 않을 것이고, 이 예제에서 알았어, 그래서 밖에 나간다

그리고 고차 수가 있습니다 합계액을위한 BDD를 작성한다면 비트, S3, 왼쪽에 표시된 BDD입니다 독점적이거나 종류가 많이 있습니다 구조체의 경우, 덧붙여 말하면, 덧셈기 안의 것들은, 알다시피, 많이 있습니다 배타적 또는 종류의 사물들

그리고 그것은 긍정적 인 논리 캐리 체인을 가지고있어 캐리가 1이되기를 원할 때 알려줍니다 그리고 부정적인 논리 캐리 체인 (carry chain)을 가지고 있습니다 상위 비트는 0이 되길 원합니다 그리고 나서 여러분은 그 두 가지에

약간의 x 또는 계산으로 꼭대기에, 너 알아 sum3 비트가 1인지 0인지를 나타냅니다 그런 다음 다른 BDD의 오른쪽을보고 수행하십시오 그것은 꽤 많은 구조를 가지고 있습니다 사실, 큰 회색 상자는 내가 강조하고있는 것입니다

그래서 저는 여기서 그것을 대략적으로 설명 할 것입니다 여기에 큰 회색 BDD가 있습니다 여기에 큰 회색의 BDD가 있습니다 이러한 것들은 기본적으로 동일한 공유 기능, 하위 기능입니다 그리고 나는, 나는 훨씬 더 강력하게, 그것들이 동일하다는 것을 말할 수있다

그래프 다른 것은 없습니다 정확히 동일합니다 그래서 우리는 흥미로운 질문을 얻습니다 어떤 사실적인 디지털 디자인 시나리오에서, 당신은 알지 못합니다

한 기능에 대한 BDD를 작성하십시오 당신은 전체 로타에 대한 BDD를 구축합니다 기능 내 말은, 아마 수백, 수백 가지 기능 그래서, 알다시피, 그것은 전혀 무리가 아닙니다

sum3 비트에 대한 BDD를 작성하고 싶습니다 그리고 나갈 비트를위한 BDD를 만들고 싶습니다 실제로 모든 것을 회색으로 두 번 만들어야합니까? BDD 패키지를 물리적으로 빌드하고 sum3 비트와 carry out 비트는 물리적으로 두 개의 복사본을 만들어야합니까? 그 회색 노드들? 어머, 나는 그랬 으면 좋겠어 그것은 매우 비효율적 일 것입니다 그리고 실제로 좋은 점이 밝혀졌습니다

뉴스 하나는 그것을 두 번 나타내지 않아도됩니다 BDD에 여러 개의 진입 점 또는 여러 개의 루트가있을 수 있습니다 권리? 하나는 그 서브 그래프를 단순히 공유 할 수 있습니다 그리고 여기에 회색으로 다시 보여 드리겠습니다

괜찮아 수행 기능이이를 사용합니다 저는 그것을 사용하는 수행 함수의 부분에 동그라미 칠 것입니다 그리고 sum3 함수가이를 사용합니다 그리고, 그것을 사용하는 방법은 알다시피, 공유 된 BDD 하위가 있습니다

기능을 수행하고 그것을 수행하기 위해 그것을 가리키는 가장자리를 전송합니다 그리고 sum3은 일부 가장자리를 사용하여 그것을 사용하기 시작합니다 그것 권리? 그래서 이러한 것들을 다중 뿌리라고합니다 노드를 가리키는 포인터가 두 개 이상 있습니다

BDD의 진입 점을 정의하는 맨 위에 단일 노드가 있습니다 그래서 이러한 것을 다중 루트 BDD라고합니다 그리고 BDD의 모든 노드는 일부 부울 함수를 나타냅니다 그래서이 멀티 루팅 아이디어는이 모든 것을 명시 적으로 악용 한 것입니다 더 나은 공유 물건

그래서 그것은 일종의 엔지니어링 아이디어이지만 멋진 아이디어 일뿐입니다 실력 있는 얼마나 효율적입니까? 오, 훌륭하게 효율적으로 일을합니다 그리고 여기 Randal Bryant로부터의 멋진 예가 있습니다 왜 2 개의 뿌리에서 멈추는가? 너는 왜 많은 뿌리가 없는지 알지

니가 원해, 그렇지? 그래서 내가 알다시피, 일종의 여기서 서브 함수를 공유합니다 너는 모든 종류의 사람들을 가질 수있다 그 것을 사용하고 싶다 마찬가지로,만큼, 내가 좋아하는만큼 따라서 이것들은 함수 집합에 큰 비용 절감 효과가 있습니다

이 공유를 최대화하여 여러 개의 개별 BDD에 대한 크기를 최소화 할 수 있습니다 실제로 제가 여러분에게 보여주고있는 것은 4 비트 가산기입니다 권리? 그래서 이것은 전체 4 비트 가산기입니다 권리? 그리고 네가 보는 것은 네 개의 합이다 비트, 알았어, 그리고 또한 수행합니다

그래서 네 가지, 음, 여덟 가지가 들어갑니다 4 개의 As와 4 개의 Bs를 볼 수 있습니다 A0 ~ 3, B0 ~ 3 및 4 합계 비트가 나오고 하나가 수행됩니다 그런데 이런 일을 할 때 얼마나 많은 돈을 저축합니까? 음, 합계의 각 비트에 대해 BDD를 별도로 작성한다면 그리고 수행하십시오 4 비트 가산기를 사용하면 51 비트가됩니다

노드 거의 12,500 노드가 될 것입니다 64 비트 덧셈기에 대해서 하지만 만약 당신이 그들을 공유하고, 그래서 31 노드 4 비트 가산기에 대해서는 571 노드, 64 비트 가산기에 대해서는 571 노드가된다 이제 봐봐

51 개 노드와 31 개 노드의 차이점 노드는별로 중요하지 않습니다 12,000 개의 노드와 600 노드는 20 개 요소 중 하나입니까? 엄청난 비용 절감 효과가 있습니다 더 커질수록 커집니다 그래서 다중 뿌리 째 아이디어, 공유 아이디어, BDD의 모든 노드가 부울이라는 사실을 악용 할 수 있다는 사실 기능 그리고 누군가 다른 사람이 그것을 사용해야한다면, 그들은 그냥 가리킬 수 있습니다

정말 멋진 일입니다 이것은 바이너리 결정 다이어그램에 대한 훌륭한 점입니다 그래서이 강의는 BDD가 데이터를 공유한다는 사실에 관한 것입니다 동일한 데이터에서 많은 부울 함수를 작성할 수있는 구조 구조 BDD의 모든 노드는 부울 함수를 사용하고 적절한 방법으로 이러한 것들을 재사용 할 수 있습니다

많은 양의 그래프가 실제로 상당한 양의 공학을 수행합니다 저금 그래서, 다음으로, 우리는 사람들이 실제로 이런 것들을 어떻게 구현하는지에 대해서는 거의 없습니다