Báo cáo Thiết kế mức hệ thống gắn với việc trộn lẫn thành phần hardware và software

hardware và software . Mô phỏng giử vai trò quan trọng trong thiết kế mức hệ thống .Ở cấp độ đặc tả ,nó cho phép mô phỏng các mô hình .Các công cụ cho phép mô phỏng các đặc tả tổng hợp đã yêu cầu .Ở cấp hiện thực những công cụ mô phỏng hổ trợ cho việc trộn lẫn hệ thống hardware và software . Thiết kế hệ thống bao gồm cả hai thành phần hardware và software không phải là vấn đề mới .Trong hướng thiết kế truyền thống thì phần cứng được thiết kế và tạo mẫu trước các thành phần software được thiết kế sau đó .Việc thiết kế hardware và software riêng rẽ gặp phải khó khăn trong việc tối ưu thiết kế hệ thống .Hướng thiết kế như vậy không tương xứng khi thiết kế những hệ thống có yêu cầu hiệu quả một cách khắt khe và thời gian thiết kế nhỏ ,hướng thiết kế chung (codesign) cho phép thiết kế những hệ thống có yêu cầu như vậy .Nguyên lý chủ yếu trong thiết kế chung là tránh sự cô lập giửa hardware và software ,chiến lược thiết kế chung cho phép thiết kế hardware ,software một cách song song với sự ảnh hưởng qua lại thông tin phản hồi của tiến trình thiết kế hardware và software .Điều này được hoàn thành nhờ những công cụ và những phương pháp hổ trợ chặt chẽ trong việc thiết kế cả hai software và hardware thông qua khung làm việc thống nhất (unified framework) .Kết quả của việc thiết kế chung hardware và software là đạt được những thiết kế chất lượng cao và giảm được thời gian thiết kế. http:// www.diachiweb.com Một sơ đồ khối cho thiết kế chung (hình 1) (hình 1) Lưu đồ thiết kế chung · Đánh giá:(estimation) Công cụ đánh giá (estimation tool) tạo ra ước lượng cho việc hiện thực (không gian và thời gian yêu cầu )cho mỗi node trong đồ thị khi hiện thực trong hardware và software .Những việc đánh giá nầy sẽ là input cho công cụ phân chia (partitioning tool). Đặc tả (design specification) Những ràng buộc (design constraints) Nhập dữ liệu (user input) Manual CPLEX (ILP) MIBS PTOLEMY Đánh giá không gian thời gian (area time estimation) Phân chia hardware ,software (hw/sw partitioning) Tổng hợp hardware (hardware synthesis Tổng hợp giao diện(interface synthesis) Sơ đồ nối dây (netlist generation) Tổng hợp software (software synthesis) Mô phỏng (simulation) Hệ thống tổng hợp (synthesized system) (layout +software ) http:// www.diachiweb.com · Phân chia (partitioning) : Sau khi thu được các đánh giá về không gian và thời gian ,bước kế tiếp trong lưu đồ thiết kế chung là phân chia .kết quả của việa phân chia là dẫn đến việc xác định công việc gồm 3 thông số · Aùnh xạ công việc (task) đó thực hiện bằng hardware hay software · Quan hệ giửa các task khi nó thực thi · Hiện thực (chọn lựa cách hiện thực chú ý đến giải thuật ,sự biến đổi (transformation),giá trị không gian ,thời gian ) . Khung làm việc trợ giúp thiết kế (design assistant framework) cho phép user thực nghiệm với những công cụ phân chia khác nhau :bằng tay , giải pháp ILP (CPLEX) , hay kinh nghiệm (heuristic MIBS) . Việc phân chia là vấn đề không phải dễ dàng .Xem xét đến đặc tả mức công việc điển hình có từ 50 đến 100 node . Mỗi task có thể ánh xạ hoặc hardware ,software ,hơn thế nữa trong mỗi công việc có vài cách lựa chọn để hiện thực . · Tổng hợp chung (cosynthesis) Một ứng dụng được phân chia vào hardware và software ,những thành phần riêng rẽ software ,hardware ,giao diện phải được tổng hợp lại .Công cụ tổng hợp đặc thù phụ thuộc vào công nghệ mong muốn.Công cụ tổng hợp hardware gồm SILAGE, VHDL, công cụ tổng hợp software thường dùng C , Assembly . Việc phát sinh giao diện phụ thuộc vào mô hình kiến trúc mong muốn · Mô phỏng chung (cosimulation): Các thành phần software ,hardware ,giao diện đã tổng hợp ,bước tiếp theo là mô phỏng hệ thống nhờ môi trường mô phỏng PLOTEMY · Kiến trúc đích (target architecture) : (hình 2) KIẾN TRÚC ĐÍCH The hardware bao gồm những thành phần có sẵn hoặc phải chế tạo thêm, và software là những chương trình chạy trên những thành phần lập trình được .Giao diện hardware ,software bao gồm nối kết logic và điều khiển phụ thuộc vào cơ chế truyền nhận dữ liệu được chon . 2.PARTITIONING : Trong phần nầy chúng ta tập trung nghiên cứu vấn đề phân chia hardware hay software cho các ứng dụng về hệ thống thời gian thực .Giả sử ta có một đặc tả ứng dụng được biểu diển bằng đồ thị SDF (synchronous data flow) ,SDF nầy chuyển thành DAG (directed acycle graph) ,DAG nầy là input cho công cụ phân chia (partitioning tool). Address bus Data bus Control bus Processor core Hardware modul Hardware modul Hardware modul Controller http:// www.diachiweb.com Có hai giai đoạn để phân chia :Phân chia nhị phân (binary partitioning ) ,phân chia mở rộng (extended partitioning) Phân chia nhị phân:là ánh xạ mỗi node của DAG sang hardware hay software và xác định thứ tự cho mỗi node . Phân chia mở rộng :Vấn đề phân chia software ,hardware không chỉ là việc ánh xạ sang software hay hardware mà trong mỗi node còn có vấn đề sử dụng những giaỉ thuật và các bộ phận tổng hợp khác nhau .Những hiện thực nầy khác nhau về đặc trưng trong không gian và thời gian trể riêng ,những tính chất nầy của node được gọi là “implementation bins”.Việc phân chia mở rộng là kết nối vấn đề ánh xạ một node sang hardware hay software trong DAG với việc lựa chọn một implementation bins thích hợp . Việc phân chia nói chung là vấn đề khó .Những thông số thiết kế có thể thường được sử dụng làm thành công thức dưới dạng vấn đề tối ưu số nguyên .Việc lập thành công thức chính xác là khó do vậy phải dùng một số kết quả heuristic để làm giảm thời gian. Tóm lại vấn đề phân chia mở rộng và phân chia nhị phân được xác địng như sau Binary partitioning Extended partitioning + 3 .Tổng hợp chung : Trong chương trước giải thuật phân chia các node của ứng dụng sang hardware ,software đã được mô tả .Việc phân chia tạo thành 3 thuộc tính cho một node :ánh xạ sang hardware hay software ,kiểu hiện thực cho ánh xạ nầy và thứ tự . Bước tiếp theo trong quá trình thiết kế là tổng hợp hệ thống trộn lẫn hardware ,software .Vấn đề tổng hợp là tổng hợp hardware ,software và các thành phần giao diện trong hiện thực cuối cùng . Mô phỏng hardware ,software ,là quá trình mô phỏng những thành phần hardware ,software của hệ thống ,trộn hardware ,software bên trong một môi trường thống nhất .Điều nầy bao gồm mô phỏng của những modun hardware ,bộ xử lý ,và software được bộ xử lý thực thi .Những yêu cầu của một môi trường mô phỏng là tạo ra phác thảo .PTOLEMY có đầy đủ công cụ nó hổ trợ hầu hết những yêu cầu nầy . 4.Mô phỏng chung : Mô phỏng hardware ,software là quá trình của thực hiện mô phỏng các thành phần hardware ,software của một hệ thống đã được trộn lẫn (tổng hợp ) hardware ,software bên trong một môi trường đồng nhất . Điều nầy bao gồm sự mô phỏng các mođun hardware ,bộ xử lý và software mà bộ xử lý sẽ thực thi . Các hướng có thể bao gồm 4.1.Mô hình chi tiết của bộ xử lý : Hardware /Software mapping and scheduling Hardware /Software mapping and scheduling implementtation bin selection http:// www.diachiweb.com Nguyên tắc chung là những thành phần của bộ xử lý có thể sử dụng mô hình những sự kiện rời rạc của kiến trúc hardware bên trong như (đường dữ liệu ,giải mã lệnh ,bus,…) mà software sẽ kết nối và thực thi trên nó . Thường dùng VHDL hay VERYLOG để mô phỏng 4.2. Mô hình bus: Đây là những sự kiện hoạt động trên ngoại vi của bộ xử lý không kết hợp thực thi software với bộ xử lý . Điều nầy có ích cho việc kiểm tra ảnh hưởng qua lại ở mức thấp như bus và bộ nhớ nhưng khó khăn cho bảo đảm chính xác mô hình hoạt động trên ngoại vi ,cũng khó khăn cho mô phỏng ảnh hưởng qua lại hardware ,software . 4.3.Mô hình kiến trúc tập lệnh : Kiến trúc tập lệnh có thể mô phỏng hiệu quả bằng chương trình C .Chương trình C là một bộ phận thông dịch cho software . Nó cập nhật trạng thái của bộ xử lý và phát sinh sự kiện đến mô hình hoạt động ngoại vi của bộ xử lý . 4.4.Mô phỏng dịch : Nguyên tắc chung là chuyển đặc tả software gắn với sự thực thi sang code tự nhiên để processor làm việc mô phỏng 4.5. Mô hình hardware : Nếu bộ xử lý tồn tại trong hình thức hardware thì hardware vật lý có thể dùng để mô hình hoá procesor trong mô phỏng . Có thể dùng FPGA prototype để mô hình hoá processor . Môi trường PTOLEMY là một môi trường mô phỏng kiểu mẫu được phát triển bởi nhóm DSP ở đại học BERKELEY California . PTOLEMY là môi trường duy nhất có khả năng trợ giúp trong việc mô phỏng chung hệ thống trộn lẫn hardware ,software .Môi trường nầy không những có khả năng mô phỏng mà còn tổng hợp hệ thống . 4.6 Một trường hợp nghiên cứu thiết kế trong môi trường Ptolemy: Phần nầy mô phỏng thiết kế một kênh điện thoại chọn cho trường hợp nghiên cứu nầy sử dụng môi trường Ptolemy cho thiết kế chung trộn lẫn phần cứng ,phần mềm . 4.6.1 Mô phỏng kênh điện thoại : Đồ thị dòng chảy tín hiệu của kênh điện thoại được trình bày ở hình 20 , việc mô phỏng được thiết kế dùng Motorola DSP 56000s cho hầu hết xử lý tín hiệu . Mô hình phần cứng của hệ thống yêu cầu theo mẫu bên cạnh DSPs , cũng như thành phần các kết nối logic . 4.6.2 Lựa chọn test case : Ở đây ta mô phỏng kênh điện thoại được trình bày ở hình 20 ,nó đại diện cho một hệ thống thực và thực hiện bằng thiết kế chung ,đầu tư và giá sản phẩm thấp , thời gian đưa ra thị trường cũng giảm xuống việc thiết kế và mô phỏng bên trong môi trường Ptolemy . 4.6.3 Giới thiệu bên trong môi trường Ptolemy : Hình 21 trình bày những thành phần cấu trúc của Plotemy . Đơn vị cơ sở của Plotemy là block những portholes cung cấp giao tiếp chuẩn để thông tin giữa các block . Một block gồm một mođun của code (“go()” method) nó gửi dữ liệu khi chạy , dữ liệu được gửi đến đầu vào của các portholes và phát sinh dữ liệu gửi ra ở đầu ra của portholes . Phương pháp “go() “ được điều khiển bởi liệt kê các định nghĩa ngữ nghỉa các mạng của block , truyền dẫn các block dùng những dòng gọi là particle . Lớp đo lường Geodesic được thiết lập để liên kết giữa các portholes . lớp plasma quản trị các particles . Cấp thấp nhất trong Plotemy là kiểu star trong block . Một nhóm (galaxy) cũng tìm được từ một block , một galaxy có thể chứa bên trong những galaxy và star. Một đích (target) cũng tìm được từ block điều khiển thực thi một ứng dụng . Trong một ứng dụng tổng hợp nó có thể tổng hợp assembly code cho DSP lập trình được . http:// www.diachiweb.com Hình 21 Những khối bên trong môi trường Ptolemy 4.6.4 Phương pháp thiết kế : Một hướng tổng quát để thiết kế chung được đề nghị ở hình 22 . Trên cơ sở các bước thiết kế chung nầy thiết kế mô phỏng kênh điện thoại sẽ được đề cập Hình 22 Phương pháp thiết kế chung dùng Ptolemy Bước 1 : Đặc tả ứng dụng , ở bước nầy được đặc tả bằng giải thuật cấp cao và mô phỏng đặc trưng . Bước 2 : Sử dụng miền SDF của môi trường Ptolemy. Bước 3 : Phân chia ra phần cứng hoặc phần mềm . Bước 5 , 6 , 7 : Mô phỏng phần cứng , cấu hình phần cứng được phát triển lên mức cao hơn và mô phỏng các đặc trưng . http:// www.diachiweb.com Bước 4 : Tổng hợp phần mềm . Tổng hợp phần cứng , phần mềm sau đó được mô phỏng ở bước 8 . Môi trường Ptolemy cho phép mô phỏng theo mức độ phát triển nâng cao của phần cứng , phần mềm trên cơ sở ràng buộc thời gian và các đặc điểm hợp lý . A. Thiết kế dùng Shared memory : Hướng nầy dùng 2 DSPs cho mô phỏng kênh full duplex của điện thoại . Ở đây DSPs được cấu hình để truyền nhận thông tin ở bộ nhớ dùng chung (Shared memory) . Hình 23 trình bày những thành phần trong môi trường Ptolemy dùng cho hệ thống này . Cấp độ trừu tượng chỉ là giải thuật mô tả trình bày ở hình 23(a) . Giải thuật phức tạp nầy bao gồm tuyến tính và không tuyến tính , độ dời tần số , pha và nhiễu . Thiết kế được xây dựng trong miền phát sinh code , tương thích đến mô hình SDF cho tính toán . Giải thuật cung cấp cho bộ phát sinh code , bộ phát sinh code hình 23(b) cũng cần mô tả kiến trúc đích . Từ đây bước tiếp là phát triển phần cứng cho hệ thống ( bước 5 , 6 , và 7 ở hình 22) . Hình 23(c) trình bày mô hình phần cứng của hệ thống bao gồm 2 DSP lập trình được tính toán qua một bộ nhớ Shared memory . Mô hình full duplex cấu tạo bởi tín hiệu từ một đầu cuối của kênh đến bộ lọc được lượng tử hoá và gửi đến DSP đầu tiên , DSP thứ hai đọc dữ liệu từ shared memory xử lý và gửi đến đầu cuối khác của kênh . Tương tự quá trình xử lý ngược được làm ngược lại . Chuyển đổi A/D được lượng tử hoá ở hình 23(e) . Hình 23(f) trình bày mô hình chuyển đổi D/A , giải thuật được chuyển đến bộ phát sinh code . Bước 4 và 5 của hình 22 phân chia và liệt kê các khối và phát sinh assembly code cho processor trong hệ thống . Đầu ra của bộ sinh code là assembly code đáp ứng giải thuật chạy trên 2 processor . Phần cứng sau đó được mô phỏng ở bước 8 của hình 22 chạy code được phát sinh bởi bộ phát sinh code . Chúng ta có thể thấy tác động lẫn nhau giữa giải thuật mô tả , mô phỏng , phát sinh code , phát triển phần cứng và mô phỏng , phần cứng được mô hình tại những mức độ khác nhau của giải thuật mô tả dùng những miền khác nhau của môi trường Ptolemy . B.Thiết kế dùng Serial port :Một kiểu thiết kế khác được lựa chọn như hình 24 được phát triển bằng tác động qua lại qua bước 4 đến bước 8 ở hình 22 . Ở đây DSPs được truyền thông tin bằng dãy cổng thay thế cho shared memory . Như đã thấy trong hình , tín hiệu từ đầu cuối của kênh được nhận bằng DSP đầu tiên (DSP1) ở đây tín hiệu được xử lý và gửi qua một dãy cổng đến DSP thứ 2 (DSP2) sau đó gửi ra một đầu cuối khác của kênh . Những khối khác như A/D , D/A được thiết kế giống như thiết kế shared memory Cấu hình phần cứng thay đổi ( như IPC delay) được cung cấp đến bộ sinh code , bộ sinh code sẽ phân chia và liệt kê lại code ở bước 4 hình 22 . Thiết kế nầy minh họa cho trường hợp với chiến lược IPC khác nhau có thể điều khiển bằng tay trong Ptolemy . Hai hệ thống nầy (shared memory va serial port) được đánh giá chú ý đến hiệu suất như IPC overhead , giá của hệ thống . 5.TỔNG KẾT: Trong đồ án nầy đề cập đến phát triển kỹ thuật cho thiết kế hệ thống xử lý tín hiệu . Thiết kế hệ thống đòi hỏi giá chính xác , hiệu suất và ràng buộc về thời gian . Những hiện thực hardware ,software thuần túy thường không gặp ràng buộc nầy bên cạnh đó một vài bộ phận của ứng dụng thì gắn với hoặc hardware , hoặc software . Từ đây những ứng dụng hướng tới http:// www.diachiweb.com những hiện thực trộn lẫn hardware , software . Những ứng dụng nầy được đặc tả tốt nhất ở mức độ Task nguyên thủy . Hướng đi đến thiết kế là thiết kế chung các thành phần hardware , software . Điều nầy cho phép những thiết kế hardware ,software là tiến trình song song , với sự hồi tiếp và ảnh hưởng lẫn nhau giữa 2 quá trình khi phát triển . Thiết kế chung cho phép khảo sát rộng lớn những trạng thái lựa chọn hiện thực , do đó hệ thống được tối ưu hóa và trọn vẹn của nó . Bốn vấn đề chính được đặt ra trong thiết kế chung mức hệ thống là : phân chia , tổng hợp , mô phỏng và quản lý phương pháp thiết kế , chúng ta cố gắng cung cấp những cách giải quyết cho vấn đề nầy như giải quyết hệ thống xử lý tín hiệu đặc tả từ SDF . 5.1 Phân chia : Phân chia nhị phân là vấn đề xác định cho mỗi node trong một ứng dụng đó là : ánh xạ một node sang hardware hay software , trình tự của sự thực thi . Phân chia mở rộng là vấn đề gắn với ánh xạ node trong đồ thị mức cao đến hardware hay software thứ tự và lựa chọn hiện thực đặc biệt cho mỗi node , mục tiêu cuối cùng của cả hai là làm nhỏ nhất tổng không gian hardware , tính đến ràng buộc tài nguyên . Giải thuật GCLP giải quyết vấn đề phân chia nhị phân ,một vài đặc điểm của giải thuật : 1 . Công nhận rằng phân chia nhị phân là tối ưu ràng buộc . GCLP dùng một đo lường giới hạn thời gian chung GC để lựa chọn thích ứng mục tiêu ánh xạ ở mỗi bước . Nếu thời gian là tranh chấp nó lựa chọn ánh xạ mà thời gian thực thi của node sẽ nhỏ nhất , nhưng nó tiêu thụ tài nguyên nhỏ nhất . 2 . Thêm vào xem xét nầy có các pha cục bộ như extremity measure ,repeller measure và normal để xét một node ánh xạ sang hardware hay software thích hợp hơn . GCLP có độ phức tạp O(|N|2). Phân chia mở rộng được giải quyết bằng giải thuật MIBS ,ý nghĩa của MIBS là mở rộng GCLP cho phân chia mở rộng mà không xây dựng những phức tạp kết hợp khác . Chiến lược phân loại những node trong đồ thị là : free node , tagged node , fixed node . Đầu tiên khởi tạo tất cả những node trong đồ thị là free , ánh xạ và hiện thực bin chưa biết , GCLP áp dụng cho tất cả các node trong tập free ,sau đó một node tagged sẽ được chọn từ tập nầy và ánh xạ của nó được quyết định bằng GCLP . Một thủ tục lựa chọn bin được dùng để tính toán và hiện thực thích hợp bin cho tagged node , nó sử dụng đo lường trước gọi là bin fraction ,nó lượng giá mỗi bin của node . Bin fraction được sử dụng tính toán đo lường độ nhạy bin tương quan đến hiện thực bin với thu giảm tổng không gian hardware . Thủ tục lựa chọn bin được chọn với độ nhạy cao nhất . Tính toán độ nhạy bin được đơn giản hóa bằng cách công nhận những node tự do còn lại hoặc chậm nhất . Tagged node trở thành fixed node và lựa chọn được một hiện thực bin . GCLP sau đó áp dụng lên tất cả các node free còn lại và trình tự được lặp cho đến khi tất cả node trong đồ thị thành cố định 5.2 Tổng hợp và mô phỏng : Tổng hợp chung là vấn đề của tổng hợp hardware ,software và thành phần giao diện của hệ thống , bắt đầu từ một DAG đã được phân chia kỹ thuật tổng hợp đạt được kiến trúc đích bao gồm : một processor đơn lập trình được và nhiều mođun hardware . Node được ánh xạ sang hardware ,software được truyền nhận dùng một ánh xạ bộ nhớ . Tổng hợp chung là phân rã DAG được phân chia thành đồ thị hardware ,đồ thị software ,và giao diện .Mỗi node trong đồ thị hardware ,software đều có kỹ thuật đại diện . Công cụ tổng http:// www.diachiweb.com hợp được sử dụng để phát sinh hiện thực cuối cùng từ những đồ thị nầy . Những công cụ có sẵn như ( HYPER và PTOLEMY ) được dùng để phát sinh hiện thực cuối cùng . Mô phỏng hardware , software là quá trình mô phỏng các thành phần hardware và software của hệ thống trộn lẫn bên trong môi trường đồng nhất ,điều nầy có nghĩa là mô phỏng mođun hardware , bộ xử lý ,software mà bộ xử lý thực thi 5.3 Quản lý phương pháp thiết kế : Chúng ta đưa ra một cơ sở hạ tầng hổ trợ quản lý hiệu quả quá trình thiết kế với tầm quan trọng là quản trị dòng thiết kế . Cơ sở hạ tầng được phát triển như DMM domain bên trong môi trường PTOLEMY có một công cụ là Designmaker đáp ứng tự động quản lý dòng chảy . 6. PHỤ LỤC 1.Môi trường PTOLEMY Ptolemy là môi trường đồng nhất trợ giúp cho sự tổng hợp và mô phỏng.Nó sử dụng kỹ thuật lập trình hướng đối tượng để mô hình những hệ thống con trong sự tự nhiên và hiệu quả nhất với một sự hợp nhất trọn vẹn. Nền tảng của nó là BLOCK, một hệ thống được mô phỏng như một Network của Block, thứ tự được quyết định bởi ngữ nghĩa trong network nghĩa là nó quyết thứ tự mà block được thự thi Đối tượng thấp nhất trong Ptolemy là loại STAR.A STAR được đặc tả bơỉ C++ ,đặc tả này bao gồm những hàm :setup(),go(),wrapup().A GALAXY cũng bắt nguồn từ BLOCK chứa những BLOCK khác bên trong.A GALAXY Ùcó thể chứa cả hai loại là Galaxy và Star. Ptolemy trợ giúp nhiều mẩu mô phỏng ,những loại thiết kế khác nhau gọi là DOMAIN .Một Domain mô tả đúng mô hình tính toán thích hợp cho một loại hệ thống con đặc thù.Một số Domain mô phỏng hiện thời được trợ giúp bao gồm:Synchronous Data Flow(SDF) ,Dynamic Data Flow(DDF),Discrete Event (DE) và Digital Hardware Modeling Environment(Thor). A Domain trong Ptolemy bao gồm tập của Block và thứ tự phù hợp với mô hình sự tính toán chung ,nó cũng trợï giúp sựï trộn lẩn giửa các mô hình này ở mức hệ thống để phát triển hệ thống hổn tạp với sự khác nhau ở mức trưù tượng. Sự trộn có thứ bậc bất cứ mô hình tính toán có thể sử dụng ở mức cao của hệ thống ,bên trong mỗi mức của hệ thống có thứ bậc nó có thể có những Block đang chưá các Domain bên ngoài.Hệ thống hổn tạp có thứ bậc thì hầu hết khác nhau từ những khái niệm của simulation backplane. 2.Độ phức tạp của giải thuật GCLP Độ phức tạp cuả giải thuật GCLP được tính như sau: S1.Tính toán GC:O(A+N) S1.1.Lượng giá tập của những node di chuyển đến phần cứng:O(1) S1.2.Tính toán thời gian hoàn thành thực tế:O(A+N). S2.Xác định tập những node sẳn sàng:O(N) S3.Tính toán thời gian thực thi hiệu quả:O(N) S4.Tinh toán đường đi dài nhất:O(A). S5.Chọn một node sẵn sàng với đường đi dài nhất lớn nhất:O(N) S6.Xác định ánh xạ và thứ tự:O(1) Trong bước S1.2 tính toán thời gian hoàn thành dùng giải thuật COMPUTE_ACTUAL_FINISH_TIME sau: Procedure COMPUTE_ACTUAL_FINISH_TIME http:// www.diachiweb.com Input:DAG với sự xác định lại ánh xạ và tưông ứng với thời gian thực thi(texec(I)) cho mỗi node i Output:Tfinish=thời gian hoàn thành của DAG Khởi tạo:dsp_finish_time=0,Tfinish=0: S1.Gán nhãn cho tất cả các node với cấp của nó S2.Gán mặt nạ cho tất cả các node cấp 0 như là node sẳn sàng S3.while (ready nodes exist){ S3.1.Chọn node sẳn sàng i:O(i) S3.2.Tìm Tstart(i):O(1) S3.3.if (i in software) Tstart(i)=max(maxj(tavail(j)),dsp_finish_time) /*j:inputs của node i*/ if (i in hardware) Tstart(i)=maxj(tavail(j)) S3.4 Cập nhật tfinish(i)=tstart(i)+texec(i):O(1) S3.5.if i là trong software: Dsp_finish_time=(dsp_finish_time>tfinish(i))? Dsp_finish_time:tfinish(i) S3.6.Cho mỗi output k của node i set tavail(k)=tfinish(i) S3.7.Cho mỗi output k của node i ,truy cập node p nối đến nó S3.7.1.Giảm bậc của node p S3.7.2.Nếu bậc của p là 0 :cộng p vào list của những node sẳn sàng S3.8.Tfinish=(Tfinish>tfinish(i))? Tfinish:tfinish(i) }:O(A+N) Procedure COMPUTE_LONGEST_PATH in