A classical approach to solve the Hypergraph bipartitioning problem is an iterative heuristic by Charles Fiduccia and Robert Mattheyses. This heuristic is commonly called the FM algorithm.
| Attributes | Values |
|---|
| rdfs:label
| - Fiduccia–Mattheyses algorithm (en)
- FM 알고리즘 (ko)
- Fiduccia-Mattheyses (nl)
|
| rdfs:comment
| - A classical approach to solve the Hypergraph bipartitioning problem is an iterative heuristic by Charles Fiduccia and Robert Mattheyses. This heuristic is commonly called the FM algorithm. (en)
- Fiduccia-Mattheyses is een algoritme om een lokale zoekactie uit te voeren. Deze methode wordt gebruikt bij het graaf-bipartioneringsprobleem (zie Grafentheorie). Hierbij is het doel het de twee kleuren van de knopen van de graaf zo aan te passen zodat er zo min mogelijk knopen van verschillende kleur met elkaar verbonden zijn. Het aantal knopen dat met elkaar verbonden is en een andere kleur bezit noemt met de knipgrootte. (nl)
- 전자공학에서 FM 알고리즘(Fiduccia Mattheyses algorithm)은 Physical Design의 작업 중 하나인 Circuit Partitioning 공정의 하나이다. 다른 공정으로는 K-L(Kernighan-Lin)알고리즘, Simulated Annealing 등이 있다. F-M(fiduccia-mattheyses) 알고리즘은 Fiduccia[1982]와 Mattheyes에 의해 노드연결 분리문제(hypergraph bipartitioning problem)를 해결하기 위해 고안된 반복해석 기법이다. 입력데이터분석: 하이퍼그래프로 이루어진 벌텍스(vertex, 디지털 Gate를 변환하면 만들어진 블록)와 하이퍼엣지, 예) Net1 C1, C2, C3, C4 n(i): Net 에 연결된 Cell(셀)의 숫자 예) n(1) = 4: net 1번에 연결되어 있는 Cell의 숫자는 4개다. 4개의 Gate가 연결되어 있다.] s(i): i Cell의 크기(어떤 Cell은 한개의 크기가 다른 것의 2,3배가 되기 때문에 Cutset을 할 때 이것을 고려해야한다.) (ko)
|
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - A classical approach to solve the Hypergraph bipartitioning problem is an iterative heuristic by Charles Fiduccia and Robert Mattheyses. This heuristic is commonly called the FM algorithm. (en)
- 전자공학에서 FM 알고리즘(Fiduccia Mattheyses algorithm)은 Physical Design의 작업 중 하나인 Circuit Partitioning 공정의 하나이다. 다른 공정으로는 K-L(Kernighan-Lin)알고리즘, Simulated Annealing 등이 있다. F-M(fiduccia-mattheyses) 알고리즘은 Fiduccia[1982]와 Mattheyes에 의해 노드연결 분리문제(hypergraph bipartitioning problem)를 해결하기 위해 고안된 반복해석 기법이다. 입력데이터분석: 하이퍼그래프로 이루어진 벌텍스(vertex, 디지털 Gate를 변환하면 만들어진 블록)와 하이퍼엣지, 예) Net1 C1, C2, C3, C4 n(i): Net 에 연결된 Cell(셀)의 숫자 예) n(1) = 4: net 1번에 연결되어 있는 Cell의 숫자는 4개다. 4개의 Gate가 연결되어 있다.] s(i): i Cell의 크기(어떤 Cell은 한개의 크기가 다른 것의 2,3배가 되기 때문에 Cutset을 할 때 이것을 고려해야한다.) p(i): i Cell에 연결된 핀즉 Net선의 개수; e.g., p(1) = 4 은 1번 Cell에는 4개의 선이 연결되었다는 의미이며, 즉 연결된 Net 4개라는 의미가 된다 C: 회로에 주어진 총 Cell의 개수; e.g., C = 13 총 C1, C2, .... C13까지 있다는 의미이다. N: 회로에 주어진 Net의 개수이다. e.g., N= 4는 즉 Net1, Net2, Net3, Net4가 있다는 의미이다. P: Net과 Cell 사이에 연결된 총 Pin의 개수; P= p(1) + … + p(C) = n(1) + … + n(N) 즉 각각의 Cell의 연결된 Pin의 개수는 각 Net에 연결된 Pin의 개수와 당연히 일치한다. r: Cutset을 위해 요구되는 Balance Factor이다. 0< r<1 출력데이터 Output: 2 partitions A& Bs.t.Cutset size는 최적의 수가 되어야 한다. 제일 작은 수가 되어야 한다. 이것이 우리가 원하는 첫 번째 목적이다. 주어진 회로를 2-way or Muti-Way를 하는데 있어서 가장 적은 Cutsize로 잘라야 한다. Balance Factor: r = |A|/(|A|+|B|) - 균형의 인자는 2-way로 나뉜 Net-Cut의 Weight 즉 균형점의 값이 된다. FM은 K-L 알고리즘과 달리 임의적으로 나누수 있다. 그렇다고 두개의 Net-Cut을 극단적으로 10:90으로 나누면 한쪽의 CPU가 처리해야하는 용량이 너무 많으므로 최대한으로 가능한 균형값을 정해 줄 필요가 있는데 이것을 Balance Factor라 한다. 반복횟수: O(P)은 Operation Time은 P 즉 총 Pin의 개수 만큼 반복해야 한다. 최적 minimum Cutset Size는 O(P) 횟수 만큼 Cell를 옮겨서 각각의 G(i)의 값의 합을 구하고 이 중에서 가장 큰 값 max sum of G(i)가 우리가 찾고자 하는 최적의 Condition 이 되는 것이다. (ko)
- Fiduccia-Mattheyses is een algoritme om een lokale zoekactie uit te voeren. Deze methode wordt gebruikt bij het graaf-bipartioneringsprobleem (zie Grafentheorie). Hierbij is het doel het de twee kleuren van de knopen van de graaf zo aan te passen zodat er zo min mogelijk knopen van verschillende kleur met elkaar verbonden zijn. Het aantal knopen dat met elkaar verbonden is en een andere kleur bezit noemt met de knipgrootte. (nl)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
