컴퓨터 산술 알고리즘의 시간 및 시간 복잡도 비교

Question

현재 칩 레벨 설계에서 구현할 때 어떤 알고리즘이 더 나은지를 찾는 프로젝트에서 작업 중입니다. 나는 이것을 FPGA 보드로 밀어 넣고있다. 나는 Verilog에서 코드를 작성하고있다. 내가 필요한 것은 비교할 내용입니다.

a) 2 가지 기능의 시간 복잡도.

b) 최악의 타이밍 예를 들어

C) 소비 전력

,

방법 1 : 자극 = mult1 * mult2;

여기서 mult1과 mult2는 두 개의 8 비트 입력입니다.

방법 2 : 자극 = ((+ mult1 mult2-100) × 100) + ((100 mult1) * (100 mult2)) mult1 mult2 및 두 8 비트 입력이

.

그래서 두 입력이 전달되고 제품이 계산 된 시간부터 칩이 제품을 계산하는 데 걸리는 총 시간을 알고 싶습니다.

내가 처리중인 알고리즘은 모두 O (n)입니다. 그래서 나는 그것이 점근 적으로 중요하지 않다는 것을 안다. 그러나 FPGA 또는 ASIC 보드에서 구현할 때 정확한 최악의 타이밍을 파악하여 기능을 향상시키려는 시도에 관심이 있습니다. 그러나 이러한 계산에 나노초가 걸리므로이를 개선하려고 노력하고 있습니다.

더 빠른 알고리즘을 가지고 있다고 주장하는 몇 개의 저널 간행물을 보았습니다. 그러나 자일링스를 사용하여 동일한 기능을 구현하고 합성 보고서를 사용할 때 다른 결과를 얻고있었습니다.

전력 소비량과 최악의 타이밍을 계산하는 소프트웨어가 있습니까? 아니면 누군가 나를 도와 줄 수있는 몇 가지 기사를 알려줄 수 있습니까?

Answer 1

시간 복잡도와 최악의 경우 타이밍은 알고리즘 작성 방법과 사용중인 대상 FPGA에 따라 달라집니다.

계산을 실행하는 데 걸리는 시간을 이해하려면 FPGA의 클록 주파수와 알고리즘을 수행하는 데 필요한 클럭 사이클 수에 따라 다릅니다. 곱셈 알고리즘이 단일주기라면 계산에 걸리는 시간은 단순히 FPGA의 클록주기가됩니다. 그러나, 대형 곱셈 회로는 그 복잡성 때문에 일반적으로 단일 사이클이 아니다. 정확히 무엇을 얻는지는 입력 코드, 합성기 및 사용하는 fpga의 종류에 따라 다릅니다.

일반적으로 FPGA 합성 도구는 합성 후 보고서에서 최악의 경우 설계 타이밍을 알려줍니다. 최악의 경우의 타이밍을 향상 시키려면 곱셈에 파이프 라인 스테이지를 추가하여 작업을 분해하고 클록 주파수를 높일 수 있습니다.

측정 소비 전력은 사용하는 FPGA와로드하는 합성 네트리스트에도 크게 의존합니다. Altera 및 Xilinx은 fpgas (아마도 다른 공급 업체)에 대한 전력 견적서를 제공하지만 벤더에 상관없는 전력 견적서가 있는지 여부는 확실하지 않습니다.

간단히 말해, 사용하려는 FPGA의 합성 도구로 작업해야하는 메트릭을 얻으려면 간단합니다.