题目

求平面上n个顶点的最近点对问题

算法设计

分治法

1．先考虑一维的情形，即线段上最近点对。

用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S|x≤m}；S2={x∈S|x>m}，S1∪S2=S ，S1∩S2=Φ，则线段上最近点对为以下三者中的距离最小者：

（1）左半边S1的最近点对

（2）右半边S2的最近点对

（3）跨越分点m的最近点对

左半边S1的最近点对和右半边S2的最近点对的求解可以递归地调用该过程。而跨越分点m的最近点对，我们可以将S1中的一点与S2中的每一点计算距离，但这将花费O(n^2)。

缘起

之前一位大一的学弟问我微积分作业，我发现当时觉得还算简单的题，现在竟然已经不会做了。

而且每当考试前我都会发现，平时努力记下的知识，大部分已经生疏了。

我一直在想，如果所有的知识都将被遗忘，那么学习的意义在哪呢？

学习？记忆?

学习多年，我相信大部分人和我一样，在认知上认为记忆只是学习的一步，但行动上记忆几乎成为学习的全部，无论是记笔记或是所谓的错题本，都是强行以记忆代替学习。

这些方法固然有效，在信息量小的时候增加强化次数以永久记忆，但在信息爆炸的现在，如何？

实验目的

设计一个MIPS指令集的CPU，

1、 基本要求：

a)    多周期
b)    包含16条指令
    i.    add addi addu sub subu 
    ii.

Verilog中的有符号数与无符号数

缘起

• 在用Verilog编写流水线CPU时，ALU需要实现add、addu、sub、subu、slt、sltu功能，分别是加、减、小于则置位的有符号和无符号版本，不过之前使用Verilog编写代码的时候从来没有考虑过符号问题，基本都是按无符号处理，除了在立即数符号拓展部分涉及到了符号

    `assign SignExtented = {{16{IMM16[15]}},IMM16};`
  

  这里相当于是手动按符号拓展。

• 那么，现在要实现的addu和add的区别在哪呢？还有溢出如何判断？

回顾

• 马上回想了下原码和补码的问题，但是这只是在有符号情况下对正负数表示的统一，现在的问题是Verilog中“+”这个运算符是认为操作数是有符号还是无符号呢？（当然，正数的情况没有区别）。马上测试了一下：
  ​

大容量存储器与文件系统

大容量存储器简介

实验目的

1. 实现一个多周期MIPS指令集的CPU，支持包括lw、sw、R-type、addi、beq、bgtz、j等指令。
2. 运行一个计算斐波那契数列的程序，初始为3，3。

实验平台

• ISE 14.7

实验过程（分析）

1. 模块化设计，主要有以下几个模块

   a) alu模块——算术逻辑单元

   b) regfile模块——寄存器文件

   c) mux模块和mux4模块——2路和4路选择器

   d) IP核生成的Mem模块——存放数据段和代码段

   e) nextpclogic模块——计算下一个PC

实验目的

• 综合前几次实验的结果，实现一个单周期MIPS指令集的CPU， 然后运行一个计算斐波那契数列的程序。

实验平台

• ISE 14.7

实验过程（分析）

1. 模块化设计，主要有以下几个模块

   a) alu模块——算术逻辑单元

   b) regfile模块——寄存器文件

   c) mux模块——选择器

   d) IP核生成的IMem模块和DMem模块——存放数据段和代码段

进程通信与同步、进程调度

进程间通信

• 进程在执行过程中，如果不被其他进程影响或影响其他进程，则称该进程是独立的，否则称为协作的。进程协作可能是出于以下几个目的：信息共享、提高计算速度、模块化设计…进程间要实现协作就需要一套通信机制（IPC），目前主要有两种模式：共享内存和消息传递。

实验目的

• 综合利用三次实验的结果，完成以下功能：

• 通过例化，向ram中0地址到13地址存入14个数，比如10-23；向ram中100地址到106地址存入7个数，比如0~6，分别代表运算符（与ALU的操作符对应），最后向ram 107地址写入-1

进程与线程

进程的概念

• 我们知道，人们通过操作系统来更方便地操作硬件，提高使用计算机的效率。早期的计算机只允许一次执行一个程序，这样的程序完全控制了系统，能访问所有的资源。但随着操作系统的功能愈加复杂，计算机的应用更加广泛，人们往往需要同时进行多个作业，因此就有了进程的概念，不同的进程同时运行，互相独立，进行不同的工作。