Máy tính CNN kiến trúc và thuận toán

Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009<br /> <br /> Kĩ thuật – Công nghệ<br /> <br /> MÁY TÍNH CNN KIẾN TRÚC VÀ THUẬT TOÁN<br /> Vũ Đức Thái - Đàm Thanh Phương (Khoa Công nghệ thông tin – ĐH Thái Nguyên),<br /> Phạm Thượng Cát (Viện Công nghệ thông tin -Viện KH&CN Việt Nam)<br /> <br /> 1. Đặt vấn đề<br /> Trong nhiều vấn đề khoa học, kĩ thuật hiện nay cần tốc độ tính toán nhanh, khối lượng<br /> tính toán lớn. Tốc độ máy tính hiện nay đã đạt gần tới giới hạn vật lí về kiến trúc mạch (hạn chế<br /> bởi trở kháng, nhiễu của vi mạch), dù các chíp đã được cải tiến không ngừng nhưng cũng không<br /> đáp ứng được những bài toán tính toán phức tạp. Con người mong muốn có thế hệ máy tính thông<br /> minh có khả năng xử lí nhiều dạng dữ liệu như khả năng của sinh vật vẫn xử lí trong cuộc sống.<br /> Cùng một thời điểm, chúng ta có thể vừa nhìn, vừa nghe, vừa nói, vừa suy nghĩ. Nghĩa là xử lí<br /> nhiều dạng dữ liệu khác nhau với tốc độ rất nhanh trong cuộc sống thực.<br /> Người ta đã nghiên cứu những khả năng xử lí của hệ thần kinh của các cơ thể sống (để có<br /> thể mô hình hóa cơ chế xử lí này trên máy tính), đã phát hiện ra tiến trình xử lí của các nơron<br /> thần kinh vừa tương tác, vừa lan truyền, vừa xử lí cục bộ từng cấp tùy theo vị trí, khả năng của<br /> các tế bào. Do vậy, một tác vụ lớn được phân cấp xử lí cho nhiều nơron đồng thời trên toàn hệ<br /> thần kinh, từ nơi nhận cảm giác đến thần kinh trung ương. Dữ liệu đưa vào xử lí của thế giới tự<br /> nhiên vô cùng phong phú, phức tạp có dạng luồng thông tin động thay đổi theo thời gian thực<br /> (các hình ảnh ta quan sát, âm thanh ta nghe được...) [1]. Bộ não đồng thời xử lí một cách độc lập<br /> cho từng loại tín hiệu vào và trả lời bằng các cư xử tương ứng thông qua các phản xạ không điều<br /> kiện và có điều kiện (khi học sinh trả lời câu hỏi kiểm tra của thầy cô giáo, đồng thời phản xạ<br /> chớp mắt khi có hạt bụi bay vào mắt).<br /> Thông qua quá trình xử lí, các nơron còn tích lũy được kinh nghiệm cho việc xử lí lần<br /> sau, do vậy, trải qua nhiều lần luyện tập các nơron còn có khả năng nâng cao hiệu năng xử lí hay<br /> nói cách khác hệ xử lí có khả năng "học".<br /> Để máy tính xử lí được các dạng dữ liệu tự nhiên (âm thanh, hình ảnh, cảm giác...) cần<br /> phải có một kiến trúc đặc biệt giống như cấu trúc của hệ thần kinh. Với khả năng xử lí tuần tự<br /> của máy PC hiện nay cho dù có tốc độ rất cao cũng không thể xử lí kịp thời và không đáp ứng<br /> được trong các tác vụ điều khiển. Do vậy, muốn có một hệ xử lí nhanh, đa luồng cần có một hệ<br /> xử lí song song đồng thời của nhiều chíp xử lí như hệ thần kinh của cơ thể sống.<br /> Công nghệ mạng nơron tế bào CNN (Cenllular Neural Networks) đã được các nhà khoa<br /> học Mỹ và Hungary phát minh ra vào năm 1988 có tốc độ xử lí của một tế bào là 1012 phép<br /> tính/giây, cả hệ có khoảng 16 000 CPU xử lí đồng thời. Đây là bước đột phá về cấu trúc của<br /> CNN là các CPU song song được kết nối thành mạng tích hợp trong một chip [2,3].<br /> 2. Kiến trúc của máy tính CNN -UM (CNN - Universal Machine)<br /> Mô hình CNN là một cấu trúc lí tưởng cho một mảng tính toán analog lập trình được. Với<br /> mảng lớn các chíp xử lí 2D, 3D cũng chỉ cần biểu diễn bởi tập các trọng số (A,B,z). Hiện nay đã<br /> có hàng trăm mẫu trong thư viện của CNN [2,3,4].<br /> Hình 1 mô tả cấu trúc một hệ CNN điển hình. Các tế bào được điều khiển bởi khối<br /> GAPU nó là một khối chứa các phần tử analog và lô gic (gọi là analogic). GAPU bao gồm thanh<br /> ghi lệnh analog (APR) chứa nhiều lệnh analog chính là các mẫu (template); thanh ghi chương<br /> trình logic (LPR) chứa các hàm lô gic cục bộ của mỗi tế bào. Tiến trình xử lí được điều khiển bởi<br /> các chuyển mạch (switch) cục bộ. Các cấu hình xử lí được lưu trong thanh ghi cấu hình chuyển<br /> <br /> 1<br /> <br /> Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009<br /> <br /> Kĩ thuật – Công nghệ<br /> <br /> mạch (SCR). Trình tự thực hiện các lệnh lôgic được lưu trong khối điều khiển analog và logic<br /> toàn cục (GACU) [6].<br /> <br /> Hình 1. Cấu trúc của một hệ CNN<br /> <br /> Phần lõi của CNN chứa các phần tử analog và logic, xung quanh có 5 khối ngoại vi cục<br /> bộ liên kết giữa các tế bào. Phần tử điều khiển và truyền thông cục bộ nhận lệnh từ SCR và điều<br /> khiển các chuyển mạch đồng thời điều khiển đầu vào/ra. Các khối LLM và LAM có thể nhận,<br /> gửi tín hiệu trực tiếp không cần qua khối GAPU; các khối LAOU và LLU lưu giá trị analog và<br /> logic cục bộ, là các giá trị analog và logic trung gian nhằm làm giảm nhiều thao tác tính toán<br /> toàn cục trong CNN. Khối SCR và LPR điều khiển các đầu ra riêng lẻ. GAPU có hai chế độ xử lí<br /> analog (tốc độ cao cho xử lí cục bộ, tốc độ thấp cho truyền nhận dữ liệu) và xử lí logic.<br /> 2.1. Đặc trưng về cơ chế hoạt động của CNN -UM<br /> - Thay đổi trạng thái theo thời gian quá độ của mạch điện (rất nhanh cỡ micro giây).<br /> - Trạng thái của mỗi tế bào biến đổi theo thời gian là tín hiệu điều khiển đưa ra cho các<br /> hệ thứ cấp thực thi các tác vụ. So sánh với máy tính PC ta thấy những điểm khác cơ bản của<br /> CNN và máy PC (H.2):<br /> <br /> Hình 2. So sánh giữa máy tính PC và CNN-UM<br /> <br /> - Mỗi đầu vào được một tế bào xử lí và đưa ra kết quả, như vậy mảng các tế bào tham<br /> gia xử lí đồng thời cho mảng tín hiệu vào. Ngoài quá trình xử lí, các tế bào còn có quá trình<br /> truyền thông tin cho nhau từ đầu mảng đến cuối mảng trên toàn hệ CNN, như vậy hệ CNN còn<br /> có tính năng như hệ thần kinh. Sau mỗi xử lí, trạng thái của tế bào được thay đổi do có sự liên<br /> kết với các tế bào xung quanh nhận được tín hiệu hồi tiếp trở lại, làm cho toàn hệ luôn ở trạng<br /> thái động (dynamic). Quá trình xử lí trên chỉ diễn ra trong thời gian quá độ của mạch điện cỡ<br /> nanô giây đến micro giây. Nếu hệ CNN có kích thước 128x128 thì có thể có khoảng 16.000 tín<br /> hiệu được xử lí đồng thời. Tín hiệu vào cho mỗi tế bào có thể là tín hiệu tương tự hoặc tín hiệu số<br /> (do phần ghép nối của mỗi tế bào cho phép nhận cả hai loại tín hiệu này). Tùy từng loại dữ liệu mà<br /> ta có thể thiết kế quá trình xử lí tương ứng cho hệ CNN. Thao tác xử lí cho mỗi tín hiệu thông tin<br /> <br /> 2<br /> <br /> Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009<br /> <br /> Kĩ thuật – Công nghệ<br /> <br /> vào như thao tác xử lí cho từng điểm ảnh trong một ảnh vào, như vậy cả hệ CNN có thể xử lí cho<br /> luồng thông tin vào giống như bài toán xử lí ảnh cho từng pixel. Hình 3 mô tả hiện tượng liên kết<br /> và trạng thái mạch điện của một tế bào trong hệ CNN. Điện áp uij là điện áp vào; điện áp xij là điện<br /> áp trạng thái; điện áp yij là điện áp ra. A(ij;kl) và B(ij;kl) là điện dẫn liên kết giữa tế bào C(i,j) và<br /> các tế bào láng giềng của nó.<br /> <br /> Hình 3. Cấu trúc bên trong và sự liên kết của một tế bào<br /> <br /> - Phương trình trạng thái điện áp của tế bào C(i,j) như sau:<br /> x ij<br /> 1<br /> C<br /> x ij<br /> A(i, j; k , l ) y kl<br /> B(i, j; k , l )u kl z ij<br /> t<br /> R<br /> C ( k ,l ) S r ( i , j )<br /> C ( k ,l ) S r ( i , j )<br /> <br /> (1)<br /> <br /> trong đó: C, R là điện dung và điện trở của mạch. A, B là điện dẫn hồi tiếp, điện dẫn vào tổng hợp<br /> từ các tế bào láng giềng, z là dòng điện ngưỡng. Điện áp đầu ra y(i,j) được tính theo công thức:<br /> 1<br /> 1<br /> (2)<br /> yij f ( xij )<br /> | xij 1 |<br /> | xij 1 |<br /> 2<br /> 2<br /> Đặc trưng cơ bản của CNN là điện áp ra có dạng hàm tuyến tính từng đoạn (piecewise<br /> linear function) có dạng:<br /> <br /> 3. Các thuật toán của CNN<br /> Chương trình xử lí trong CNN được thực hiện thông qua các lệnh (template - mẫu). Mỗi<br /> lệnh ứng với một template. Trong thư viện của CNN có các template cơ bản và ngày càng được<br /> bổ sung phong phú hơn. Người lập trình còn có thể tự tìm cho mỗi bài toán những template đặc<br /> trưng tùy theo yêu cầu xử lí. Khi xử lí bài toàn, chúng ta phải xây dựng mô hình toán học cho bài<br /> toán và tìm các template sau đó cho thực thi với các phép xử lí analogic.<br /> 3.1 Ví dụ về bài toán xử lí ảnh: Nhập vào một ảnh đen trắng, tìm các điểm thay đổi độ<br /> xám (màu trắng thành đen hoặc màu đen thành trắng so với điểm trước nó) trên ảnh vào.<br /> Để xử lí bài toán trên ta có các tác vụ CNN:<br /> <br /> 3<br /> <br /> Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009<br /> <br /> Kĩ thuật – Công nghệ<br /> <br /> - Nạp ảnh.<br /> - Chạy Tem1.<br /> - Chạy Tem2.<br /> - Thực hiện phép OR với hai ảnh.<br /> - Đưa ra kết quả.<br /> Lưu đồ thực hiện trên CNN như hình 4:<br /> <br /> Hình 4. Lưu đồ bài toán xử lý ảnh<br /> <br /> Nếu gọi các điểm trắng là 0 điểm đen là 1, ta có các template của bài toán xử lí ảnh trên:<br /> - TEM1:<br /> 0 0 0<br /> A<br /> <br /> 0<br /> <br /> 2 0<br /> <br /> B<br /> <br /> 0 0 0<br /> 2 2 0<br /> <br /> 0 0 0<br /> <br /> 0 0 0<br /> <br /> 0 0 0<br /> <br /> 0 0 0<br /> 0 2<br /> 2<br /> <br /> z= -15<br /> <br /> - TEM2:<br /> A<br /> <br /> 0<br /> <br /> 2 0<br /> <br /> 0 0 0<br /> <br /> B<br /> <br /> z= -15<br /> <br /> 0 0 0<br /> <br /> Mã chương trình AMC:<br /> 1. LOADTEM<br /> 2. LOADTEM<br /> 3. COPY<br /> 4. RUNTEM<br /> 5. RUNTEM<br /> 6. RUNLOG<br /> 7. COPY<br /> <br /> >FF80,APR1<br /> >FF60,APR2<br /> A_MC, > FF40, LAM1<br /> APR1, LAM1, LAM1, LLM1<br /> APR2, LAM1, LAM1, LLM2<br /> OR, LLM1, LLM2,LLM3<br /> L_C2M, LLM3, >FF00<br /> <br /> ; Nạp mẫu TEM1<br /> ; Nạp mẫu TEM2<br /> ; Copy ảnh từ bộ nhớ vào chip<br /> ; Chạy TEM1<br /> ; Chạy TEM2<br /> ; Chạy toán tử logic OR<br /> ; Copy ảnh từ chip sang bộ nhớ<br /> <br /> Bước 1: Nạp mẫu TEM1 (cấu hình của các ngắt trong tế bào cho các lệnh trên như hình 5):<br /> <br /> 4<br /> <br /> Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009<br /> <br /> Kĩ thuật – Công nghệ<br /> <br /> 1). Mẫu TEM1 được nạp vào hai tụ Cu và Cx qua hai ngắt sw2, sw1<br /> 2). Tụ Cx phóng điện, dòng điện chạy trong mạch nạp vào các phần tử<br /> đến khi ổn định qua ngắt sw0 (thực hiện quá trình quá độ trong mạch)<br /> 3). Nạp LAM2 vào LLM1 qua ngắt sw4<br /> <br /> Hình 5. Quá trình nạp TEM1 (1,2,3)<br /> <br /> (Quá trình nạp TEM2 cũng thực hiện tương tự các bước (a,b,c), mẫu TEM2 được đưa vào<br /> LLM2)<br /> Bước 2: Thực hiện phép OR với hai TEM1, TEM2<br /> Bước 3: Đưa ra kết quả: Hai mẫu TEM1, TEM2 được xử lí qua phép OR sau đó đưa kết<br /> quả ra LLM3.<br /> <br /> Hình 6. Nạp kết quả vào LLM3<br /> <br /> 3.2. Ví dụ về giải phương trình vi phân đạo hàm riêng<br /> Mô hình dòng chảy một chiều trong kênh dẫn nước được mô tả bằng hệ phương trình đạo<br /> hàm riêng Saint venant có hai biến vận tốc dòng chảy Q(x,t) (đơn vị m3/s) và độ cao mực nước<br /> h(x,t) (đơn vị m). Người ta đo số liệu tại một số vị trí tại một số thời điểm. Dựa trên việc giải hệ<br /> phương trình ta có thể xác định giá trị Q, h tại những điểm khác trong miền không gian (những<br /> vị trí không đo được) và thời điểm nào đó trong miền thời gian [8].<br /> S ( x, t )<br /> t<br /> <br /> Q ( x, t )<br /> t<br /> <br /> [<br /> <br /> Q( x, t )<br /> x<br /> <br /> Q ( x, t ) 2<br /> ]<br /> h ( x, t )<br /> S ( x, t )<br /> gS ( x, t )<br /> x<br /> x<br /> <br /> q<br /> <br /> gIS ( x, t ) gJS ( x, t )<br /> <br /> kq q(<br /> <br /> Q ( x, t )<br /> S ( x, t )<br /> <br /> Vì bài toán có 2 biến hàm và là hàm hai biến, ta cần xây dựng 2 lớp CNN 1D. Sau khi mô<br /> hình hóa theo dạng của CNN chúng ta có các template cho bài toán như sau:<br /> Mẫu trên lớp h:<br /> <br /> 5<br /> <br />