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

Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009 Kĩ thuật – Công nghệ 1 MÁY TÍNH CNN KIẾN TRÚC VÀ THUẬT TOÁN Vũ Đức Thái - Đàm Thanh Phương (Khoa Công nghệ thông tin – ĐH Thái Nguyên), Phạm Thượng Cát (Viện Công nghệ thông tin -Viện KH&CN Việt Nam) 1. Đặt vấn đề 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 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ế 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 đá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 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. 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í nhiều dạng dữ liệu khác nhau với tốc độ rất nhanh trong cuộc sống thực. 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ó 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 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 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ệ 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ự 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 (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 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 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ạ chớp mắt khi có hạt bụi bay vào mắt). 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 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 nói cách khác hệ xử lí có khả năng "học". Để 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 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ự 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 đượ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ệ 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. Công nghệ mạng nơron tế bào CNN (Cenllular Neural Networks) đã được các nhà khoa 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 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 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]. 2. Kiến trúc của máy tính CNN -UM (CNN - Universal Machine) 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 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 đã có hàng trăm mẫu trong thư viện của CNN [2,3,4]. 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 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 ghi lệnh analog (APR) chứa nhiều lệnh analog chính là các mẫu (template); thanh ghi chương 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 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 Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009 Kĩ thuật – Công nghệ 2 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 toàn cục (GACU) [6]. Hình 1. Cấu trúc của một hệ CNN 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 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 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, 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à 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 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í 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. 2.1. Đặc trưng về cơ chế hoạt động của CNN -UM - Thay đổi trạng thái theo thời gian quá độ của mạch điện (rất nhanh cỡ micro giây). - 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 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 CNN và máy PC (H.2): Hình 2. So sánh giữa máy tính PC và CNN-UM - 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 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 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 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 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 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ỡ 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 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ố (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à 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 Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009 Kĩ thuật – Công nghệ 3 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 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 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 á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à các tế bào láng giềng của nó. Hình 3. Cấu trúc bên trong và sự liên kết của một tế bào - Phương trình trạng thái điện áp của tế bào C(i,j) như sau: ij jiSlkC kl jiSlkC klij ij zulkjiBylkjiAx Rt x C rr ),(),(),(),( ),;,(),;,( 1 (1) 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 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: ||||)( 1x 2 1 1x 2 1 xfy ijijijij (2) Đặ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 linear function) có dạng: 3. Các thuật toán của CNN 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 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 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 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 toán và tìm các template sau đó cho thực thi với các phép xử lí analogic. 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 độ 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. Để xử lí bài toán trên ta có các tác vụ CNN: Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009 Kĩ thuật – Công nghệ 4 - Nạp ảnh. - Chạy Tem1. - Chạy Tem2. - Thực hiện phép OR với hai ảnh. - Đưa ra kết quả. Lưu đồ thực hiện trên CNN như hình 4: Hình 4. Lưu đồ bài toán xử lý ảnh 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: - TEM1: 000 020 000 A 000 022 000 B z= -15 - TEM2: 000 020 000 A 000 220 000 B z= -15 Mã chương trình AMC: 1. LOADTEM >FF80,APR1 ; Nạp mẫu TEM1 2. LOADTEM >FF60,APR2 ; Nạp mẫu TEM2 3. COPY A_MC, > FF40, LAM1 ; Copy ảnh từ bộ nhớ vào chip 4. RUNTEM APR1, LAM1, LAM1, LLM1 ; Chạy TEM1 5. RUNTEM APR2, LAM1, LAM1, LLM2 ; Chạy TEM2 6. RUNLOG OR, LLM1, LLM2,LLM3 ; Chạy toán tử logic OR 7. COPY L_C2M, LLM3, >FF00 ; Copy ảnh từ chip sang bộ nhớ 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): Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009 Kĩ thuật – Công nghệ 5 1). Mẫu TEM1 được nạp vào hai tụ Cu và Cx qua hai ngắt sw2, sw1 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ử đến khi ổn định qua ngắt sw0 (thực hiện quá trình quá độ trong mạch) 3). Nạp LAM2 vào LLM1 qua ngắt sw4 Hình 5. Quá trình nạp TEM1 (1,2,3) (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 LLM2) Bước 2: Thực hiện phép OR với hai TEM1, TEM2 Bước 3: Đưa ra kết quả: Hai mẫu TEM1, TEM2 được xử lí qua phép OR sau đó đưa kết quả ra LLM3. Hình 6. Nạp kết quả vào LLM3 3.2. Ví dụ về giải phương trình vi phân đạo hàm riêng 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 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 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ệ 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 vị trí không đo được) và thời điểm nào đó trong miền thời gian [8]. ( , ) ( , )S x t Q x t q t x 2( , ) [ ] ( , ) ( , ) ( , )( , ) ( , ) ( , ) ( , ) ( ( , ) q Q x t Q x t h x t Q x tS x t gS x t gIS x t gJS x t k q t x x S x t 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ô hình hóa theo dạng của CNN chúng ta có các template cho bài toán như sau: Mẫu trên lớp h: Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009 Kĩ thuật – Công nghệ 6 Ch = 1; Rh=1 ; ][ xb2 1 0 xb2 1 AQh ; A h = [0 1 0]; ][ b q B ih 010 ; z = 0. Mẫu trên lớp Q CQ = 1; RQ =1; ][ 1i 1i 1i 1iQ xhb2 Q 0 xhb2 Q A ; ])([ x2 gbh JIgb x2 gbh A iihQ B Q = kqqi[ 0 1 0] ; z=0; Thuật toán được mô phỏng trên Matlab có kết quả: a) Giá trị của Q b) Giá trị của h Hình 7. Kết quả giải phương trình Saint venan 4. Ứng dụng và sự phát triển của CNN Với những tính năng đặc biệt CNN đã được áp dụng vào nhiều lĩnh vực: chẩn đoán các triệu chứng trong cơ thể con người; điều khiển rô bốt biết di chuyển. Nhiều bài toán yêu cầu xử lí với chế độ thời gian thực đã được thực hiện. Một số dạng ứng dụng gần đâylà [7]: - Chụp ảnh phân tích tia lửa điện (20000 ảnh/giây). - Theo dõi đa mục tiêu. - Hệ thống an toàn trên ô tô. Về mặt lí thuyết có các hướng phát triển: - Xây dựng tập mẫu và các chương trình đảm bảo tính ổn định. - Phân loại các mẫu trong sự truyền sóng không gian - thời gian. - Nghiên cứu các thuật toán liên quan đến phương trình vi phân đạo hàm riêng và các mẫu cho CNN đa lớp. - Nghiên cứu độ phức tạp tính toán, thuật toán cho máy tính sóng tế bào tương tự- logic trong việc xử lí luồng dữ liệu. 5. Kết luận Tuy mới ra đời nhưng CNN có nhiều tiềm năng ứng dụng trong tương lai với những bài toán mà hiện nay máy PC không thể giải quyết được. Bài báo chỉ nêu được một số nét khái quát có tính giới thiệu về máy tính tương tự CNN. Hiện nay, CNN mới được tập trung nghiên cứu tại một số nước (Italia, Hungary, Tây Ban Nha, Thổ Nhĩ Kì, Mỹ, Hàn Quốc, Nhật Bản...). Tại Việt Nam, CNN mới có một số nhóm nghiên cứu tại Viện Công nghệ thông tin - Viện KH&CN Việt Nam; ĐH Thái Nguyên, ĐH Bách khoa Hà Nội. Trong tương lai cần sự quan tâm, Tạp chí Khoa học & Công nghệ - Số 1(49)/năm 2009 Kĩ thuật – Công nghệ 7 và một lực lượng lớn các nhà nghiên cứu để tiếp cận với trình độ thế giới và phát huy khả năng ứng dụng tại Việt Nam Tóm tắt Bài viết này giới thiệu, phát triển rộng rãi những kiến thức cơ bản về kiến trúc và thuật toán xử lí của máy tính CNN-UM. Bài viết này gồm 04 phần: Phần đặt vấn đề nói lên nhu cầu một hệ tính toán mới đáp ứng các bài toán tính toán lớn hiện nay là máy tính PC hiện nay không giải quyết được. Phần 2 nêu lên những kiến trúc cơ bản của hệ CNN để có thể thực thi được những tác vụ theo yêu cầu. Phần 3 nêu những thuật toán và những bài toán ứng dụng đã triển khai trên máy tính CNN-UM. Phần 4 nêu những tiềm năng, sự phát triển và các thách thức trong tương lai. Summary This paper has the purpose introducing and expanding the basic knowledge of architect and processing algorithm of CNN Universal Machine (CNN-UM). It consists of 4 parts: Introduction, Part 2 gives the more detail of structure inside CNN chip. Part 3 introduces the examples of CNN application (images processing and solving Partial Differential Equation). Part 4 give a trend of development and application of CNN in the future. The conclusion explains the studies and research CNN scene in Vietnam and over the world. Tài liệu tham khảo [1] V.D. Thai, P.T. Cat, "Solving Saint venant Equation Describing an Open Hydraulic Channel Employing Cellular Neural Network" CISA 09. [2]. Leon O. Chua and L. Yang (1998), "Cellular Neural Networks: Theory", IEEE Trans. Circuits Syst. Vol.35. [3]. Leon O. Chua and L. Yang (1998), "Cellular Neural Networks: Application", IEEE Trans. Circuits Syst. Vol.35. [4]. Tibo Kozek, Leo O. Chua, Tamás Roska, Dietrich Wolf, Ronald Tetzlaff, Frank Puffer and Ka’roly Lots (1995). “Simulating Nonlinear Waves and Partial Differential Equatios via CNN – Part II: Typical Examples” IEEE Trans. Circuits Syst. Vol.42, NO 10. [5]. Tamás Roska (2003), "Computational and Computer complexity of analogic cellular wave computers" Journal of Circuits Sysem and Computer Vol. 12 No. 4. [6]. Tamás Roska (2005), "Cellular Wave Computers for Brain-Like Spatial-Temporal SensoryComputing" IEEE Circuits and System Magazine Second quarter. [7] Tamás Roska, Leon O. Chua (2003), "The CNN Universal Machine: 10 years later" Journal of Circuit, Systems, and Computer, Vol. 12, No. 4. 377-388. [8]. Tamás Roska, Leo O. Chua, Dietrich Wolf, Tibo Kozek, Ronald Tetzlaff and Frank Puffer (1995), “Simulating Nonlinear Waves and Partial Differential Equatinos via CNN – Part I: Basic Techniques” IEEE Trans. Circuits Syst. Vol.42, NO 10.