Các thuật toán cho các máy tính Analog – Đọc báo cùng IP

Your computer performs most tasks well. For word processing, certain computations, graphic arts and web surfing, the digital box on your desk is the best tool for the job. But the way your computer works, with its style of mathematics that relies on the binary code system of “on” and “off” 1s and 0s, isn’t ideal for solving every problem.

• Máy tính của bạn thực hiện tốt hầu hết các nhiệm vụ. Để xử lý văn bản, các phép toán, nghệ thuật đồ họa và lướt web, hộp kỹ thuật số trên bàn của bạn là công cụ tốt nhất cho công việc. Nhưng cách máy tính của bạn hoạt động, với phong cách toán học dựa trên hệ thống mã nhị phân “bật” và “tắt” 1 và 0, đấy không phải cách lý tưởng để giải quyết mọi vấn đề.

That’s why researchers such as Zoltán Toroczkai, professor in the Department of Physics and concurrent professor in the Department of Computer Science and Engineering at the University of Notre Dame, are interested in reviving analog computing at a time when digital computing has reached its maximum potential.

• Đó là lý do tại sao các nhà nghiên cứu như Zoltán Toroczkai, giáo sư Khoa Vật lý và đồng thời cũng là giáo sư tại Khoa Khoa học và Kỹ thuật Máy tính tại Đại học Notre Dame, quan tâm đến việc phục hồi phương thức điện toán analog trong khi tại thời điểm điện toán kỹ thuật số đạt đến khả năng tối đa.

Toroczkai and collaborators have been working toward developing a novel mathematical approach that will help advance computation beyond the digital framework. His most recent paper, published in Nature Communications, describes a new mathematical, analog “solver” that can potentially find the best solution to NP-hard problems.

• Toroczkai và các cộng tác viên đang làm việc để phát triển một cách tiếp cận thuật toán mới sẽ giúp thúc đẩy tính toán vượt ra ngoài khuôn khổ kỹ thuật số. Bài báo gần đây nhất của ông được xuất bản trên tạp chí Nature Communications mô tả một thuật toán mới được gọi là “người giải” analog có khả năng tìm ra giải pháp tốt nhất cho các vấn đề về các bài toán NP-hard (một dạng trong toán học).

NP-hardness is a theory of computational complexity, with problems that are famous for their difficulty. When the number of variables is large, problems associated with scheduling, protein folding, bioinformatics, medical imaging, and many other areas are nearly unsolvable with known methods. After testing their new method on a variety of NP-hard problems, the researchers concluded their solver has the potential to lead to better, and possibly faster, solutions than can be computed digitally.

• NP-hardness là một lý thuyết về độ phức tạp tính toán, với các vấn đề nổi tiếng về độ khó của chúng. Khi số lượng biến số lớn, các vấn đề liên quan đến lập lịch, gấp protein, phân tích tin sinh học, hình ảnh y tế và nhiều lĩnh vực khác gần như không thể giải quyết được bằng các phương pháp đã biết. Sau khi thử nghiệm phương pháp mới của họ trên nhiều vấn đề NP-hard, các nhà nghiên cứu kết luận rằng bộ giải của họ có khả năng dẫn đến các giải pháp tốt hơn và có thể nhanh hơn, có thể được tính toán bằng kỹ thuật số.

Analog computers were used to predict tides from the early to mid-20th century, guide weapons on battleships and launch NASA’s first rockets into space. They first used gears and vacuum tubes, and later, transistors, that could be configured to solve problems with a range of variables. They perform mathematical functions directly. For instance, to add 5 and 9, analog computers add voltages that correspond to those numbers, and then instantly obtain the correct answer. However, analog computers were cumbersome and prone to “noise” — disturbances in the signals — and were difficult to re-configure to solve different problems, so they fell out of favor.

• Các máy tính analog đã được sử dụng để dự đoán thủy triều từ đầu đến giữa thế kỷ 20, điều khiển vũ khí trên tàu chiến và phóng tên lửa đầu tiên của NASA vào không gian. Đầu tiên họ sử dụng các bánh răng và ống chân không, và sau đó, các bóng bán dẫn, có thể được cấu hình để giải quyết các vấn đề với một loạt các biến. Họ thực hiện các chức năng toán học trực tiếp. Ví dụ, để thêm 5 và 9, các máy tính tương tự sẽ thêm các điện áp tương ứng với các số đó và sau đó ngay lập tức có được câu trả lời đúng. Tuy nhiên, các máy tính tương tự rất cồng kềnh và dễ bị “nhiễu” – nhiễu tín hiệu – và rất khó để thiết lập lại cấu hình để giải quyết các vấn đề khác nhau, vì vậy chúng không được ưa chuộng.

Digital computers emerged after transistors and integrated circuits were reliably mass produced, and for many tasks they are accurate and sufficiently flexible. Computer algorithms, in the form of software, are sets of instructions that tell the computer hardware how to perform. Because the process is restricted to the use of 0s and 1s, this also makes their programming simpler, and allowed digital computing to dominate for nearly 70 years.

• Máy tính kỹ thuật số xuất hiện sau khi các bóng bán dẫn và mạch tích hợp được sản xuất hàng loạt, và đối với nhiều tác vụ, chúng chính xác và đủ linh hoạt. Các thuật toán máy tính, ở dạng phần mềm, là các bộ hướng dẫn cho phần cứng máy tính biết cách thực hiện. Bởi vì quá trình này bị hạn chế trong việc sử dụng 0 và 1, điều này cũng làm cho việc lập trình của họ đơn giản hơn và cho phép máy tính kỹ thuật số thống trị trong gần 70 năm.

However, their restrictions may prevent digital computers from solving NP-hard problems with many variables. One such problem is the “Traveling Salesman” problem, in which a salesperson must start in one city and return to that city at the end of a trip, but in between, must travel to all the different cities on a list. What’s the most efficient route among all the points? The problem becomes exponentially more challenging with the addition of more cities. The difficulty with such optimization problems, Toroczkai noted, is “while you can always come up with some answer, you cannot determine if it’s optimal. Determining that there isn’t a better solution is just as hard as the problem itself.”

• Tuy nhiên, các hạn chế của chúng có thể ngăn máy tính kỹ thuật số giải quyết các vấn đề về NP-hard với nhiều biến. Một trong những vấn đề như vậy là vấn đề “Nhân viên bán hàng du lịch”, trong đó một nhân viên bán hàng phải bắt đầu ở một thành phố này và trở về thành phố khác khi kết thúc chuyến đi, nhưng ở giữa, phải đi đến tất cả các thành phố khác nhau trong danh sách. Tuyến đường nào hiệu quả nhất trong số tất cả các điểm? Vấn đề trở nên khó khăn hơn theo cấp số nhân với việc bổ sung thêm nhiều thành phố. Khó khăn với các vấn đề tối ưu hóa như vậy, Toroczkai lưu ý thêm rằng “trong khi bạn luôn có thể đưa ra một số câu trả lời, bạn không thể xác định liệu nó có tối ưu hay không. Xác định rằng không có giải pháp nào tốt hơn cũng khó như chính vấn đề.”

A challenge for analog computing rests with the design of continuous algorithms. Unlike digital computing, which has a long history in algorithm development, algorithms for analog computers lack a similar knowledge base and thus are very difficult to design. Toroczkai’s approach is different from the types of algorithms for digital computers, in all aspects.

• Một thách thức đối với điện toán analog nằm ở việc thiết kế các thuật toán liên tục. Không giống như điện toán kỹ thuật số, có lịch sử phát triển thuật toán lâu dài, các thuật toán cho máy tính analog thiếu một nền tảng kiến thức tương tự và do đó rất khó thiết kế. Cách tiếp cận của Toroczkai khác với các loại thuật toán cho máy tính kỹ thuật số, về mọi mặt.

The next step is to design and build devices based on this approach, a process that will be tackled within Notre Dame’s College of Engineering. The analog computers would be built for specific tasks, and not for everyday computing needs. This work is part of a larger-scale, multi-institutional effort, called Extremely Energy Efficient Collective Electronics (EXCEL), led by Notre Dame’s Suman Datta, Freimann Chair of Engineering and professor of electrical engineering, in collaboration with Sharon Hu, professor of computer science and engineering.

• Bước tiếp theo là thiết kế và chế tạo các thiết bị dựa trên phương pháp này, quá trình này sẽ được thực hiện trong Trường Cao đẳng Kỹ thuật của Notre Dame. Các máy tính analog sẽ được xây dựng cho các nhiệm vụ cụ thể chứ không phải cho các nhu cầu tính toán hàng ngày. Công trình này là một phần của một dự án lớn với nỗ lực của nhiều tổ chức, được gọi là Điện tử tập thể hiệu quả năng lượng cực lớn (EXCEL), do Suman Datta, Chủ tịch Kỹ thuật Freimann và giáo sư kỹ thuật điện, phối hợp với Sharon Hu, giáo sư Khoa học và Kỹ thuật Máy tính.
  

“There are mostly engineering problems that need to be solved at this point, such as spurious capacities and better noise control, but it’s going to get there,” Toroczkai said. “Ideally I would like to see that you have this box on your desk that is your scheduler. And it is going to do much better of a job than your regular computer.”

• “Hầu hết các vấn đề kỹ thuật cần được giải quyết vào thời điểm này, chẳng hạn như công suất giả và kiểm soát tiếng ồn tốt hơn, nhưng nó sẽ có thể được giải quyết,” Toroczkai nói. “Lý tưởng nhất là tôi muốn thấy rằng bạn có chiếc hộp này trên bàn là lịch trình của bạn. Và nó sẽ làm việc tốt hơn nhiều so với máy tính thông thường của bạn.”

Highlight Vocabulary

       1. binary (adj) /ˈbaɪnəri/

relating to a system of counting, used in computers, in which only the numbers 0 and 1 are used → Nhị phân

All computer equipment deals only in binary code.

Tất cả các thiết bị máy tính chỉ giải quyết trong hệ thống mã nhị phân.

       2. concurrent (adj)

happening or existing at the same time → Đồng thời

The judge imposed concurrent sentences totaling 14 years for the attacks on the girls.

Thẩm phán tuyên án các bản án đồng thời tổng cộng 14 năm cho các vụ tấn công các cô gái.

       3. complexity (n)

/kəmˈplek.sə.ti/

the state of having many parts and being difficult to understand or find an answer to → Sự phức tạp

There are a lot of complexities surrounding this issue.

Có rất nhiều sự phức tạp xung quanh vấn đề này.

       4. bioinformatics (n) \ˌbī-ō-in-fər-ˈma-tiks\

the collection, classification, storage, and analysis of biochemical and biological information using computers especially as applied to molecular genetics and genomics → Tin sinh học

The use of computer databases for protein identification is one of many software techniques collectively termed bioinformatics.

Việc sử dụng cơ sở dữ liệu máy tính để nhận dạng protein là một trong nhiều kỹ thuật phần mềm được gọi chung là tin sinh học.

       5. circuit (n) /ˈsɜːkɪt/

a path for an electric current to flow through → Mạch điện

The most advanced chip technology, which uses circuits 65 nanometers apart, loses almost half of its power to leakage.

Công nghệ chip tiên tiến nhất, sử dụng các mạch cách nhau 65 nanomet, giảm gần một nửa công suất do rò rỉ.

       6. algorithm (n)

/ˈæl.ɡə.rɪ.ðəm/

a set of mathematical instructions or rules that, especially if given to a computer, will help to calculate an answer to a problem -> Thuật toán

Music apps use algorithms to predict the probability that fans of one particular band will like another.

Các ứng dụng âm nhạc sử dụng thuật toán để dự đoán xác suất người hâm mộ của một nhóm cụ thể sẽ thích nhóm khác.

       7. restriction (n)

/rɪˈstrɪk.ʃən/

an official limit on something → Sự hạn chế

The president urged other countries to lift the trade restrictions.

Tổng thống kêu gọi các nước khác dỡ bỏ các hạn chế thương mại.

       8. exponentially (adj)/ˌek.spəˈnen.ʃəl/

An exponential rate of increase becomes quicker and quicker as the thing that increases becomes larger → theo cấp số nhân

We are looking for exponential growth in our investment

Chúng tôi đang tìm kiếm sự tăng trưởng theo cấp số nhân trong đầu tư của chúng tôi

       9. optimization (n) /ˌɒp.tɪ.maɪˈzeɪ.ʃən/

the act of making something as good as possible → sự tối ưu hóa

The airline’s scheduling optimization program ensures that it serves the maximum number of passengers.

Chương trình tối ưu hóa lịch trình của hãng hàng không đảm bảo rằng nó phục vụ số lượng hành khách tối đa.

       10. spurious (adj) \ˈspjʊə.ri.əs\

false and not what it appears to be, or (of reasons and judgments) based on something that has not been correctly understood and therefore false → Giả

some of the arguments in favor of shutting the factory are questionable and others downright spurious.

một số lập luận ủng hộ việc đóng cửa nhà máy là nghi vấn và những lý lẽ khác hoàn toàn giả mạo.

Người dịch: Nhung Nguyễn

Nguồn: sciencedaily